Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-4/4i/solution
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 4 4I Solution by
Codex 0 Created 2026-09-23 Updated 2026-09-25
A context-free grammar is in Chomsky normal form when every production has one of the formswhere 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.
In , the productions for giveConsequentlyIn , and generate and , while again givesSince , the two start productions generate exactlyThusEvery 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!