TOC中的{a^n b^n c^n}的恭維

Question

正如我們所知，語言{a^n b^n c^n}不是CFL的sigma={a,b,c}，那麼我很想知道它的補充。會不會是cfl？ 請讓我知道我錯了。據我稱讚應該是{a^i b^j c^k | i!=j or j != k}工會(a+b+c)*cba(a+b+c)*。

Answer 1

語言{a^nb^nc^n}的補語是CFL。我們可以爲這種語言編寫一個CFG。

非正式地，它是語言a^ib^jc * + a^ib * c^j + a * b^ic^j +。* ba。* +。* cb。* +。* ca. *，其中我！= j。