Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/4h/c/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 , De Morgan's laws would give
contradicting 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 are non-context-free.
A concrete choice is . Words outside form a regular language. Among words inside it, membership in means the first two counts or the last two counts differ. Each unequal-count comparison has a context-free grammar: for with , use , ; for , replace by . Append any number of 's, or prefix any number of 's for the analogous 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.

New to topics? Read the docs here!