试图证明 {a^ib^ic^i} 的补集是上下文无关的

Question

我试图证明 L= {a^ib^ic^i : i >= 1} 的补集是上下文无关的。L 补码是：{w 是 {a,b,c}* 上的一个词*：w 不在 L 中}。

众所周知，上下文无关语言在联合下是封闭的。因此，我试图将我的语言（{a^ib^ic^i} 的补集）划分为上下文无关的子集，其中它们的联合必须是上下文无关的。谁能帮我找到子集？每次我尝试这样做，最终都会得到 L*！

谢谢。

Answer 1

注意：L在下文中，我省略了不包含空字符串的约束，但这只需要进行小的调整。

\n\n

考虑。aibjck

\n

如果i=j然后j=k你有。相反，如果或，则补码的部分由字符串组成（补码的其余部分是直接的）。aibicii\xe2\x89\xa0jj\xe2\x89\xa0kaibicia*b*c*

\n

换句话说，\n

L = { aibjck | i=j } \xe2\x88\xa9 { aibjck | j=k }

\nand\n \n很容易证明上述方程中的每个子集都是上下文无关的。正如你所说，上下文无关语言在并集下是封闭的，但在交集下它们不是封闭的；因此，尽管不是，但它是上下文无关的。

L' = { aibjck | i\xe2\x89\xa0j } \xe2\x88\xaa { aibjck | j\xe2\x89\xa0k }

L'L

\n