我阅读了多个答案，说明如果一种语言不是上下文无关的，那么它的补语是上下文无关的（如果我错了，请纠正我）。反之亦然吗？上下文无关语言的补语是上下文无关的吗？
问问题
14907 次
1 回答
6
这两种说法都不正确。上下文无关语言的补语可以是上下文无关的，也可以不是上下文无关的；非上下文无关语言的补语可以是上下文无关的，也可以不是。
每种常规语言都是上下文无关的。正则语言在补语下是封闭的，所以正则语言的补语是正则的。因此，任何常规语言及其补语都是一对互补的上下文无关语言。
补语是上下文无关的非上下文无关语言的经典示例是{ww|w∈{0,1}*}. （它的补语是上下文无关的证明在这个问题的答案中。）
对于补语也不是上下文无关的非上下文无关语言，一个简单的例子是有效字符串都是对的语言{(i, x) i halts on input x}（其中i是图灵机的描述）。该语言不是上下文无关的，但它是递归可枚举的。它的补码甚至不是递归可枚举的。（见维基百科）
于 2015-12-13T01:33:10.280 回答