# Examples of context-free languages with a non-context-free complements

Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia: For $$A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\quad\text{and}\quad B = \{\mathtt a^m \mathtt b^n \mathtt c^n;~m, n ∈ ℕ_0\},$$ both $$A$$ and $$B$$ are context-free, but their intersection $$A ∩ B$$ is not. Since context-free languages are closed under unions, they can’t be closed under complementation as well.

However, this only shows that one of the three languages $$A$$, $$B$$, and $$\overline A \cup \overline B$$ is a context-free language with a non-context-free complement, but not for which one of these this is true. So what is it?

Also, is there a minimal and elegant example of a context-free language with a non-context-free complement, maybe over a binary alphabet?

The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown using the pumping lemma; see here). Its complement $L_2 = \{a,b\}^* \setminus L_1$ is context-free (as shown here). This gives a simple and elegant example of a context-free language (over a binary alphabet) whose complement is not context-free, as you requested.
The example you see on Wikipedia: put $A=\{a^n b^n c^m\}$, $B=\{a^m b^n c^n\}$. It's easy to see $\overline{A}$ and $\overline{B}$ are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore $\overline{A} \cup \overline{B}$ is a context-free language with a non-contextfree complement $A \cap B=\{a^n b^n c^n\}$.
In the same vein, the language $\{a^n b^m c^n d^m\}$ is not context-free but its complement is.
• @David Richerby: IMO the $\overline{\{ww\}}$ example might be more elegant than $\overline{\{a^n b^n c^n\}}$ or $\overline{\{a^n b^n c^m d^m\}}$, but it's more complex to prove, while the other two are mechanical. – sdcvvc Dec 25 '13 at 20:23
• You must have meant $\{a^nb^mc^nd^m\}$ in your second example. – Yuval Filmus Dec 1 '15 at 15:40