prove the complement of a language is context free

Question

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?

Answer 1

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.

Answer 2

Yes, L is not context free. The intuition behind this is that L= {a$^n$b$^n$ | n $\geq$1} is itself a context free language. This can be represented with a pushdown automata making use of its stack; however, in the case of L= {a$^n$b$^n$c$^n$ | n $\geq$1} when you get to checking the stack for c, the stack is empty... (fill the stack with n a's, then decrease the stack but n b's, but now your stuck- no way to verify n c's). You could construct your PDA a different way, but then it would non-deterministically jump around and violate the language property a$^n$b$^n$c$^n$ .

All regular languages are context free, but not all context free languages are regular. Yes, regular languages are closed under complement but not context free languages. So there is no guarantee that the complement of your L is context free because your language L isn't context free and that doesn't matter because context free languages are not closed under complement. However If you had a Context Free language, then the set difference between it and a regular language is guaranteed to be context free.

The complement of your language is context free. To prove this, take the complement of your language to derive the language L$_1$, then use the pumping lemma for context freedom on L$_1$.