= Solution
<Context-free languages> are closed under <union>: use a new start symbol with alternatives for two renamed <context-free grammars>. If they were closed under <complement> in $\Sigma^*$, <De Morgan's laws> would give
$$
L_1\cap L_2=\Sigma^*\setminus\bigl((\Sigma^*\setminus L_1)\cup(\Sigma^*\setminus L_2)\bigr),
$$
contradicting the preceding <intersection> example. Therefore \b[some CFL has a non-context-free <complement>]. This is an existence argument; it does not assert that both <complements> of the particular $L_1,L_2$ are non-context-free.
A concrete choice is $L=\{a,b,c\}^*\setminus\{a^n b^n c^n:n\geq0\}$. Words outside $a^*b^*c^*$ form a <regular language>. Among words inside it, membership in $L$ means the first two counts or the last two counts differ. Each unequal-count comparison has a <context-free grammar>: for $a^i b^j$ with $i>j$, use $T\to aTb\mid A$, $A\to aA\mid a$; for $i<j$, replace $A$ by $B\to bB\mid b$. Append any number of $c$'s, or prefix any number of $a$'s for the analogous $b,c$ comparison. Taking these <unions> gives a <context-free language> whose <complement> is the non-context-free equal-three-count language. These productions are definitions of the example, not a restriction to strict <Chomsky normal form>.
Back to article page
