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 \{ϵ\}$.

Introduce nonterminals for the terminals and one for the pair $bb$:Because the original start symbol occurs on a right-hand side, take a fresh start symbol $S_0$. After eliminating the unit production $S\to T$, one grammar in Chomsky normal form isThe original grammar generates exactlyThe displayed grammar generates the same set: $AS$ adds an $a$ on the left, $SU$ adds one $bb$ pair on the right, and $CC$ terminates the derivation with $cc$. Since the original grammar does not generate $ϵ$,

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 nonterminals and $a$ is a terminal symbol; one may additionally allow the new start production $S_0\to ϵ$ when the language contains the empty string, provided $S_0$ never appears on a right-hand side.

The standard conversion proceeds as follows.

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 $ϵ$ at the start-symbol stage. For example,is already in Chomsky normal form and generates the infinite language $\{a^n:n\ge 1\}$, so its conversion may be the grammar itself.

A context-free grammar is in Chomsky normal form when every production has one of the formswhere $A,B,C$ are nonterminals and $a$ is a terminal. One may additionally allow $S\to ϵ$ when the empty word belongs to the language, usually with the restriction that the start symbol does not occur on a right-hand side.

An $ϵ$-production has the form $A\to ϵ$. A unit production has the form $A\to B$ for nonterminals $A,B$.

In $G_1$, the productions for $T$ giveConsequentlyIn $G_2$, $X$ and $Y$ generate $a$ and $b$, while $T\to TX\mid TY\mid c$ again givesSince $Z\to TX$, the two start productions $S\to XZ\mid YZ$ generate exactlyThusEvery production of $G_2$ has the required binary-nonterminal or single-terminal form, so $G_2$ is the Chomsky-normal-form grammar for the nonempty part of $L(G_1)$.