Mathematical Foundation of Computer Science

DHARM

306 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

We see that, the new grammar still has some new unit productions. Unit productions
S → D and C → D are the useless productions because grammar doesn’t have any production
derive from D that terminates on terminal string. So remove these productions.
It has another, unit production A → B. Thus can remove while adding the productions
A → b B | b b.
Hence we get the grammar G′ (free from unit production)
S → aAa | B | bB | bb | aCaaa
A → aAa |bB |bb
B → bB | bb
C → aCaaa
where L(G′) = L(G) [Reader may verify it]

Example 11.25. Consider the grammar
S → A | b b
A → B | a
B → S | b
Remove all unit productions from the grammar.
Sol. l First we remove the production A → B so, we must add two more productions i.e.,
(+) A → S[∴ B → S]
(+) A → b [∴ B → b]
Thus grammar becomes
S → A | b b
A → S | b | a
B → S | b
l Next, remove the unit production B → S so we can add the following productions, i.e.
(+) B → A[∴ S → A]
(+) B → b b[∴ S → b b]
Now the grammar becomes
S → A | b b
A → S | b | a
B → A | b b | b
l Next, remove the unit production B → A so we add the productions
(+) B → S[∴ A → S]
(+) B → b [∴ A → b]
(+) B → a [∴ A → a]
Hence the grammar becomes
S → A | b b
A → S | b | a
B → S | b b | b | a
This grammar again has the unit production B → S, which is not terminative. So, there
is the existence of a cycle of unit productions in ths grammar. Therefore, to simplify the gram-
mar that contains cyclic case of unit productions an alternative approach is used, which is
discussed below :