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

Question Detail: 

Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia. But 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, 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?

Asked By : k.stm

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19266

Answered By : D.W.

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.