12
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The question asks for "minimal and elegant" and these examples are way more complex than the simple example given by @D.W. in his answer. $\endgroup$
    – David Richerby
    Dec 24, 2013 at 16:23
  • 3
    $\begingroup$ @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. $\endgroup$
    – sdcvvc
    Dec 25, 2013 at 20:23
  • $\begingroup$ You must have meant $\{a^nb^mc^nd^m\}$ in your second example. $\endgroup$
    – Yuval Filmus
    Dec 1, 2015 at 15:40
  • $\begingroup$ Yes, thanks for the fix (I see I made the same error in the comment, too late to edit now). $\endgroup$
    – sdcvvc
    Dec 1, 2015 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.