DHARMNON-REGULAR GRAMMARS 305Example 11.23. Consider the grammar
S → S + T | T
T → T H F | F
F → (S) | a
Remove unit productions from the grammar.
Sol. 1. Remove the unit production S → T, thus we can add following productions i.e.,
l T ⇒ T ⇒ F, so add production S → T H F.
l T ⇒ F ⇒ a, so add production S → a.
l T ⇒ F ⇒ (S), so add production S → ( S ).
2.Remove the unit production T → F, thus we can add following productions i.e.,
l F ⇒ (S), so add production T → (S).
l F ⇒ a, so add production T → a.
3.No other production is the unit production.
Hence grammar left with following productions which are free form unit productions.
S → S + T | T H F | a | ( S )
T → T H F | (S) | a
F → (S) | a
Example 11.24. Consider the grammar G has following productions
S → A | B | C
A → a A a | B
B → b B | b b
C → a C a a a | D
Find the grammar G′, which has no unit productions, that generates the language L(G), i.e.
L(G′) = L(G).
Sol. Since grammar G has 3 unit productions S → A, S → B and S → C so remove these
productions from the grammar and add new productions so that new grammar generates same
language.
1.Remove the unit production S → A, thus we can do following
l S ⇒ A ⇒ a A a; S generates a A a; so add production S → a A a.
l S ⇒ A ⇒ B; S generates B; so add production S → B.
2.Remove the unit production S → B, thus we can do following
l S ⇒ B ⇒ b B; S generates b B; so add production S → b B.
l S ⇒ B ⇒ b b; S generates b b; so add production S → b b.
3.Remove the unit production S → C, thus we can do following
l S ⇒ C ⇒ a C a a a; S generates a C a a a; so add production S → a C a a a.
l S ⇒ C ⇒ D; S generates D; so add production S → D.
Hence Grammar becomes
S → aAa | B | bB | bb | aCaaa | D
A → aAa | B
B → bB | bb
C → aCaaa | D