11
$\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?

$\endgroup$

migrated from cstheory.stackexchange.com Dec 25 '13 at 2:39

This question came from our site for theoretical computer scientists and researchers in related fields.

15
$\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.

$\endgroup$
12
$\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.

$\endgroup$
  • $\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 '13 at 16:23
  • 2
    $\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 '13 at 20:23
  • $\begingroup$ You must have meant $\{a^nb^mc^nd^m\}$ in your second example. $\endgroup$ – Yuval Filmus Dec 1 '15 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 '15 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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