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

Question

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

正如我们所知，上下文无关的语言在联合下关闭。因此，我试图将我的语言（{a^i b^i c^i}的补语）分成无上下文的子集，其中的联合必须是上下文无关的。任何人都可以帮我找到子集？每次尝试时，我都会以L *结束！

谢谢。

Answer 1

注意：在下面，我忽略了约束L不包括空字符串，但只需要一个小的调整。

---

考虑aibjck。

如果i=j和j=k那么你有aibici。相反，如果i≠j或j≠k，那么您有补充aibici。

换句话说，

L = { aibjck | i=j } ∩ { aibjck | j=k }

和

L' = { aibjck | i≠j } ∪ { aibjck | j≠k }

可以很容易地显示，在上面的方程的每个子集是上下文无关。正如你所说，上下文无关的语言在工会下被关闭，但它们在交集下不会被关闭;因此，即使 L不是， L'也是上下文无关的。