我看到在这种语言中，当我们决定 m=n; 那么我们就没有b了；所以我们不能用 c's 来比较它们。所以，我认为它不应该是 CFL。
但下面的解决方案表明它是 CFL
在上面给出的解决方案中，L2 CFL 是否正确？
问问题
1066 次
1 回答
2
语言 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 是彼此的子集，所以它们必须相等。
于 2020-02-04T14:14:53.320 回答