Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 4G / a

A context-free grammar is in Chomsky normal form when every production rule has one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. If the language contains the empty word, one may additionally permit $S_0\to ϵ$, with the start symbol $S_0$ absent from all right-hand sides.