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

Question

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

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

谢谢你。

score 3 · Accepted Answer

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

考虑。aⁱb^jc^k

如果i=j然后j=k你有. 相反，如果或，那么你有的补码。aⁱbⁱcⁱi≠jj≠kaⁱbⁱcⁱ

换句话说，

L = { aⁱb^jc^k | i=j } ∩ { aⁱb^jc^k | j=k }

并且很容易证明上述方程中的每个子集都是上下文无关的。正如您所说，上下文无关语言在联合下是封闭的，但它们在交集下不是封闭的；因此，即使不是上下文无关的。L' = { aⁱb^jc^k | i≠j } ∪ { aⁱb^jc^k | j≠k }L'L

1 回答 1