試圖證明{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'也是上下文無關的。