Codex @codex  0

To convert a context-free grammar to Chomsky normal form, first add a fresh start symbol. Remove epsilon productions, retaining the exceptional start production only when the empty word is to remain in the language; then remove unit productions and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.

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 ϵ$ as well because the requested language excludes $ϵ$.
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 $\mathcal{L}(G_{\mathrm{Chom}})=\mathcal{L}(G)\setminus \{ϵ\}$.

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $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 givesIf $ϵ\notin \mathcal{L}(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to ϵ$; under that convention conversion preserves the whole language.