= Solution
A <context-free grammar> is in <Chomsky normal form> when every production is of one of the forms
$$
A\to BC,
\qquad A\to a,
$$
where $A,B,C$ are <nonterminal symbols> and $a$ is a <terminal symbol>. Under this strict convention there is no <epsilon production>, so such a grammar cannot generate the <empty word>. Conversion of an arbitrary grammar therefore gives
$$
\boxed{\mathcal L(G_{\rm Chom})=\mathcal L(G)\setminus\{\epsilon\}.}
$$
If $\epsilon\notin\mathcal L(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to\epsilon$; under that convention conversion preserves the whole language.
Back to article page
