Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/4h/a/solution
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 4H a Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-05
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!