= Solution
A <context-free grammar> is in <Chomsky normal form> when every production has the form $A\to BC$ or $A\to a$, where $A,B,C$ are <nonterminal symbol>[nonterminals] and $a$ is a <terminal symbol>; one may additionally allow the new start production $S_0\to\epsilon$ when the language contains the <empty string>, provided $S_0$ never appears on a right-hand side.
The standard conversion proceeds as follows.
* Introduce a fresh start symbol $S_0$ and $S_0\to S$. This changes $N$ only when the old start symbol occurs on a right-hand side or when a protected start symbol is needed to preserve $\epsilon$.
* Find all nullable nonterminals, add productions obtained by omitting nullable occurrences, and remove the original $\epsilon$-productions except the permitted $S_0\to\epsilon$. This leaves $N$ unchanged.
* Eliminate each <unit production> $A\to B$ by adding to $A$ the non-unit productions reachable through its transitive closure. This leaves $N$ unchanged.
* Delete non-generating symbols and then unreachable symbols. This is the only simplification stage that can shrink $N$.
* In every right-hand side of length at least two, replace a terminal $a$ by a fresh nonterminal $T_a$ with $T_a\to a$. New nonterminals are needed exactly for terminals that occur in such mixed or long productions.
* Break every right-hand side of length at least three into binary productions, introducing fresh nonterminals for successive suffixes. New nonterminals are needed exactly when such long productions remain.
The terminal alphabet $\Sigma$ may be kept unchanged throughout, although unused terminals may be discarded by convention. Every stage preserves the generated language, with the explicit protection of $\epsilon$ at the start-symbol stage. For example,
$$
S\to SS\mid a
$$
is already in <Chomsky normal form> and generates the infinite language $\{a^n:n\geq1\}$, so its conversion may be the grammar itself.
Back to article page
