Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-4/4i/solution

A context-free grammar is in Chomsky normal form when every production has one of the forms
where are nonterminals and is a terminal. One may additionally allow when the empty word belongs to the language, usually with the restriction that the start symbol does not occur on a right-hand side.
An -production has the form . A unit production has the form for nonterminals .
In , the productions for give
Consequently
In , and generate and , while again gives
Since , the two start productions generate exactly
Thus
Every production of has the required binary-nonterminal or single-terminal form, so is the Chomsky-normal-form grammar for the nonempty part of .

New to topics? Read the docs here!