= Solution
A <context-free grammar> is in <Chomsky normal form> when every production has one of the forms
$$
A\to BC,
\qquad
A\to a,
$$
where $A,B,C$ are nonterminals and $a$ is a terminal. One may additionally allow $S\to\epsilon$ 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 $\epsilon$-production has the form $A\to\epsilon$. A <unit production> has the form $A\to B$ for nonterminals $A,B$.
In $G_1$, the productions for $T$ give
$$
L_{G_1}(T)=\{c\}\{a,b\}^*.
$$
Consequently
$$
L(G_1)
=\{\epsilon\}
\cup
\{a,b\}c\{a,b\}^*a.
$$
In $G_2$, $X$ and $Y$ generate $a$ and $b$, while $T\to TX\mid TY\mid c$ again gives
$$
L_{G_2}(T)=\{c\}\{a,b\}^*.
$$
Since $Z\to TX$, the two start productions $S\to XZ\mid YZ$ generate exactly
$$
L(G_2)=\{a,b\}c\{a,b\}^*a.
$$
Thus
$$
\boxed{L(G_2)=L(G_1)\setminus\{\epsilon\}}.
$$
Every 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)$.
Back to article page
