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

  • $\begingroup$ 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? $\endgroup$ – 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\\ $


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.