Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/4h/a/solution

In strict Chomsky normal form, every production of a context-free grammar is or , with nonterminal symbols and 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 , generated by , is therefore not generated by any strict CNF grammar.
The convention matters: extended Chomsky normal form permits with excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.

New to topics? Read the docs here!