patternModerate
Examples of context-free languages with a non-context-free complements
Viewed 0 times
freelanguageswithnonexamplescomplementscontext
Problem
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?
$$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?
Solution
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.
Context
StackExchange Computer Science Q#19266, answer score: 17
Revisions (0)
No revisions yet.