abe*_*out 0 complexity-theory context-free-grammar formal-languages context-free-language
我阅读了多个答案，指出如果一种语言不是上下文无关的，那么它的补充就是上下文无关的（如果我错了，请纠正我）。相反的情况是这样吗？上下文无关语言的补充是上下文无关的吗？
这两种说法都不是真的。上下文无关语言的补语可以是上下文无关的，也可以不是上下文无关的；非上下文无关语言的补充可以是上下文无关的，也可以不是。
每种常规语言都是上下文无关的。正则语言在补语下是封闭的，所以正则语言的补语是正则的。因此，任何常规语言及其补语都是一对互补的上下文无关语言。
补语是上下文无关的非上下文无关语言的经典示例是{ww|w?{0,1}*}。（其补语与上下文无关的证据在此问题的答案中。）
对于补语也不是上下文无关的非上下文无关语言，一个简单的例子是有效字符串都是成对的语言{(i, x) i halts on input x}（其中i是图灵机的描述）。该语言不是上下文无关的，但可以递归枚举。它的补码甚至不能递归枚举。（见维基百科）