= Solution
The standard <conversion of a context-free grammar to Chomsky normal form> proceeds as follows:
<# Add> a fresh start symbol $S_0$ with $S_0\to S$.
<# Find> the nullable nonterminals, add the variants obtained by omitting nullable occurrences, and remove all <epsilon productions>. Omit $S_0\to\epsilon$ as well because the requested language excludes $\epsilon$.
<# Remove> every <unit production> $A\to B$ by copying the non-unit productions reachable from $B$ to $A$.
<# Remove> nonterminals that are unreachable from $S_0$ or cannot derive a terminal word.
<# 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$.
<# Replace> each right-hand side of length greater than two by a chain of binary productions using fresh nonterminals.
Each remaining production is of the required binary or terminal form, and these transformations preserve every nonempty generated word. Thus \b[$\mathcal L(G_{\rm Chom})=\mathcal L(G)\setminus\{\epsilon\}$.]
Back to article page
