# Transform grammar to Chomsky Normal Form

Question:

S → abSab | baSba | TT

T → aTa| bTb | ε

S-> abSab | baSba | TT | T

T-> aTa | bTb | aa | bb

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

• Welcome to COMPUTER SCIENCE @SE. English not being my first language, I see two interpretations for ε could be replaced by T (with one a bit sloppy). What shall it mean? Does this appear in the original grammar? – greybeard Oct 7 '20 at 8:32

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\\$$