Language $L=\{a^n b^n c^n : n\geq1\}$ is not context free and it is known (please correct me if I am wrong). What i would like to know is will the complement of this language be a context free, if yes, how can I prove it?
[Math] prove the complement of a language is context free
context-free-grammarformal-languages
Best Answer
You can write $\overline{L}$ as the non-disjoint union of the four languages $$ \overline{a^*b^*c^*} \cup \{a^ib^jc^k : i \neq j \} \cup \{a^ib^jc^k : i \neq k\} \cup \{a^ib^jc^k : j \neq k\}. $$ The first one is regular and so context-free. For the second one, let's write it as a union of two languagues: $$ \{a^i b^j c^k : i > j \} \cup \{a^i b^j c^k : i < j\}. $$ We can write the first language also as $$ \{a^i a^j b^j c^k : i \geq 1 \}. $$ Hopefully you can show that this is context-free, and deduce that the entire complement is context-free.