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.
