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。