任何上下文无关语言的补语都是上下文无关的吗？
Is the complement of any context free language context free?
我阅读了多个答案，这些答案说明如果一种语言不是上下文无关的，那么它的补语就是上下文无关的（如果我错了请纠正我）。相反的情况是否如此？上下文无关语言的补充是上下文无关的？
两种说法都不正确。上下文无关语言的补充可以是上下文无关的，也可以不是；非上下文无关语言的补语可以是上下文无关的也可以不是。
每种常规语言都是上下文无关的。正则语言在补语下是封闭的，因此正则语言的补语是正则的。因此，任何常规语言及其补充语言都是一对互补的上下文无关语言。
补语是上下文无关的非上下文无关语言的经典例子是{ww|w∈{0,1}*}。 （它的补码是上下文无关的证明在 this question 的答案中。）
对于补语也不是上下文无关的非上下文无关语言，一个简单的例子是有效字符串都是对{(i, x) i halts on input x}的语言（其中i是对图灵机）。该语言不是上下文无关的，但它是递归可枚举的。它的补码甚至不是递归可枚举的。 （参见 Wikipedia）
我阅读了多个答案，这些答案说明如果一种语言不是上下文无关的，那么它的补语就是上下文无关的（如果我错了请纠正我）。相反的情况是否如此？上下文无关语言的补充是上下文无关的？
两种说法都不正确。上下文无关语言的补充可以是上下文无关的，也可以不是；非上下文无关语言的补语可以是上下文无关的也可以不是。
每种常规语言都是上下文无关的。正则语言在补语下是封闭的，因此正则语言的补语是正则的。因此，任何常规语言及其补充语言都是一对互补的上下文无关语言。
补语是上下文无关的非上下文无关语言的经典例子是{ww|w∈{0,1}*}。 （它的补码是上下文无关的证明在 this question 的答案中。）
对于补语也不是上下文无关的非上下文无关语言，一个简单的例子是有效字符串都是对{(i, x) i halts on input x}的语言（其中i是对图灵机）。该语言不是上下文无关的，但它是递归可枚举的。它的补码甚至不是递归可枚举的。 （参见 Wikipedia）