Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 4H (Automata and Formal Languages)

In strict Chomsky normal form, every production of a context-free grammar is $A\to BC$ or $A\to a$, with $A,B,C$ nonterminal symbols and $a$ a terminal symbol. Such a derivation cannot produce the empty word: it starts with one nonterminal symbol, and every step either increases the symbol count or replaces one symbol by one symbol. The context-free language $\{\epsilon \}$, generated by $S\to \epsilon$, is therefore not generated by any strict CNF grammar.

The convention matters: extended Chomsky normal form permits $S\to \epsilon$ with $S$ excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.

The context-free languages $L_1=\{a^n{b}^n{c}^m:n,m\ge 0\}$ and $L_2=\{a^m{b}^n{c}^n:n,m\ge 0\}$ have context-free grammars $S\to TC$, $T\to aTb\mid \epsilon$, $C\to cC\mid \epsilon$, and $S\to AT$, $A\to aA\mid \epsilon$, $T\to bTc\mid \epsilon$, respectively.

Their intersection is $L=\{a^n{b}^n{c}^n:n\ge 0\}$. Suppose $L$ satisfied the pumping lemma for context-free languages with length $p$. In a decomposition $a^p{b}^p{c}^p=uvwxy$ with $|vwx|\le p$ and $|vx|>0$, the window $vwx$ cannot meet both the $a$ and $c$ blocks. Pumping down changes at least one count and leaves at least one count unchanged. Thus the three counts are unequal, or the word order is invalid, contrary to the pumping lemma for context-free languages. Hence CFLs are not closed under intersection.

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 }^{\ast }$, De Morgan's laws would givecontradicting the preceding intersection example. Therefore 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{\}}^{\ast }\setminus \{a^n{b}^n{c}^n:n\ge 0\}$. Words outside $a^{\ast }{b}^{\ast }{c}^{\ast }$ 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.