我看到在这种语言中,当我们决定 m=n; 那么我们就没有b了;所以我们不能用 c's 来比较它们。所以,我认为它不应该是 CFL。
但下面的解决方案表明它是 CFL
在上面给出的解决方案中,L2 CFL 是否正确?
我看到在这种语言中,当我们决定 m=n; 那么我们就没有b了;所以我们不能用 c's 来比较它们。所以,我认为它不应该是 CFL。
但下面的解决方案表明它是 CFL
在上面给出的解决方案中,L2 CFL 是否正确?
语言 L = {a^mb^nc^k | if (m = n) then (n = k)} 是上下文无关语言,原因正是在第二个推导中给出的:条件 if (m = n) then (n = k) 不仅在 m = n 和 n = k,而且当 m 不等于 n 时。如果条件是 (m = n) 和 (n = k),则该语言将不是上下文无关的,因为该条件等价于 m = n = k。
我们可以通过证明 L 中的任何内容都在 L2 中来证明该语言是无上下文正确的推导,反之亦然。
假设一个字符串 w 在我们的语言 L 中。那么 m = n 或者不是。如果 m = n,则 n = k。但是字符串 w 在 L2 中,因为 L2 是两种语言的并集,其中一种包含 n = k 的所有字符串。如果 m = n 不是这种情况,那么字符串 w 在 L2 中,因为 L2 是两种语言的并集,另一种是 m 和 n 不相等的所有字符串的语言。所以 L 中的任何字符串都在 L2 中。
假设字符串 w 在 L2 中。那么要么 m = n 为假,要么 n = k 为真。假设 m = n 为假。那么条件 if (m = n) then (n = k) 是空虚的(因为假设是假的,并且一切都来自矛盾)。如果 n = k 为真,那么无论假设的真值如何,蕴含 if (hypothesis) then (n = k) 必须为真。所以 L2 中的任何字符串都在 L 中。
因为 L 和 L2 是彼此的子集,所以它们必须相等。