Transform grammar to Chomsky Normal Form

Question

Question:

S → abSab | baSba | TT

T → aTa| bTb | ε

My answer: Eliminate ε rules:

S-> abSab | baSba | TT | T

T-> aTa | bTb | aa | bb

Correct answer:

S → abSab | baSba | TT | abab | baba | T

T → aTa | bTb | aa | bb

I want to know why abab and baba in S.

For me, ε could be replaced by T so that S-> abSab | baSba | TT | T

Answer 1

I am not really sure what you are asking in your question, but here is the complete transformation into Chomsky-Normal-Form. The provided solution seems to be wrong, if they are really trying to get rid of the $\varepsilon$.

Step 1. Eliminate $\varepsilon$-rules

Every occurrence of $T$ could be $\varepsilon$, so like you already stated in your question the result is the following. Note however that $\varepsilon$ itself is part of the language, so even though you are eliminating $\varepsilon$-rules, $\varepsilon$ itself should appear in the production rules.

$S \to abSab \mid baSba \mid TT \mid T \mid \varepsilon,\\ T \to aTa \mid aa \mid bTb \mid bb$

Step 2. Eliminate chain rules (rules of the form $A \to B$, $B \to \mathrm{expression}$)

$S \to abSab \mid baSba \mid TT \mid aTa \mid aa \mid bTb \mid bb \mid \varepsilon,\\ T \to aTa \mid aa \mid bTb \mid bb$

Step 3. Replace terminals (except if there is only one terminal on the right hand side)

$S \to T_aT_bST_aT_b \mid T_bT_aST_bT_a \mid TT \mid T_aTT_a \mid T_aT_a \mid T_bTT_b \mid T_bT_b \mid \varepsilon,\\ T \to T_aTT_a \mid T_aT_a \mid T_bTT_b \mid T_bT_b,\\ T_a \to a,\\ T_b \to b$

Step 4. Shorten rules

$S \to T_a \mid T_bH_2 \mid TT \mid T_aH_3 \mid T_aT_a \mid T_bH_4 \mid T_bT_b \mid \varepsilon,\\ T \to T_aH_3 \mid T_aT_a \mid T_bH_4 \mid T_bT_b,\\ T_a \to a,\\ T_b \to b,\\ H_1 \to T_bH_{11},\\ H_{11} \to SH_{12},\\ H_{12} \to T_aT_b,\\ H_2 \to T_aH_{21},\\ H_{21} \to SH_{22},\\ H_{22} \to T_bT_a,\\ H_3 \to TT_a,\\ H_4 \to TT_b\\ $