QUESTION
S → aSB|bB
B → aA|b
S → abAB|ba,
A → aaa,
B → aA|bb
and
S → abAaA|abAbb|ba,
A → aaa
are equivalent.
Example 6.1
Consider G = ({A, B}, {a, b, c}, A, P) with productions
A → a|aaA|abBc,
B → abbA|b
Using the suggested substitution for the variable B, we get the grammar Ğ
with productions
A → a|aaA|ababbAc|abbc,
B → abbA|b
The new grammar Ğ is equivalent to G. The string aaabbc has the derivation
A ⇒ aaA ⇒ aaabBc ⇒ aaabbc
in G, and the corresponding derivation
A ⇒ aaA ⇒ aaabbc
in Ğ.
Notice that, in this case the variable B and its associated production are still in the grammar even though they can no longer play a part in any derivation. We will next show such unnecessary productions can be removed from a grammar.
6. Eliminate all useless productions from the grammar.
S → aS|AB|λ,
A → bA,
B → AA.
What language does this grammar generate?
7. Eliminate all useless productions from
S → a|aA|B|C,
A → aB| λ,
B → Aa,
C → cCd,
D → ddd|Cd
8. Eliminate all λ- productions from
S → aSSS
S → bb| λ.
9. Eliminate all λ- productions from
S → AaB|aaB,
A → λ,
B → bbA| λ.