200 l;l Theory of Computer Science
(Actually, (ii) covers (i) as A E W(A)). Now, we define G I =(VN, ~, PI'S),
where PI is constructed using step 2 for every A E ~v.
Before proving that G] is the required grammar, we apply the construction
to an example.
EXAM PLE 6.10
Let G be S ~ AB, A ~ a. B ~ C Ib, C ~ D, D ~ E and E ~ a. Eliminate
unit productions and get an equivalent grammar.
Solution
Step 1 V;'o(S) = {S},
Wj(S) = WoeS} u 0
Hence W(S} = {S}. Similarly,
W(A} = {A},
Wee} = {E}
Wo(B} = {B}, WI(B) = {B} u {C} = {B, C}
W 2 (B) = {B. C} u {D}. W 3 (B) = {B, C, D} u {E}, W 4 (B} = W 3 (B}
Therefore,
W(B} = {B, C, D, E}
-Similarly,
Wo(C) = {C},
Therefore.
Hence,
W(C) = {C, D, E}, Wo(D} = {D}
Thus.
WeD} ={D, E}
in G',
Step 2 The productions in Gj are
S ~ AB.
A ~ a.
B ~ b Ia, C ~ a,
By construction. G] has no unit productions.
To complete the proof we have to show that L(G'} = L(G I }.
Step 3 L(G') = L(G}. If A ~ a is in PI - P, then it is induced by B ~ a
in P with B E W(A} , a eo V v . B E W(A} implies A ~ B. Hence, A ~ B
.
~
~
=> a. So, if A => a, then A ~ a. This proves L(G j } \;;; L(G'}.
G'
G,
G'
To prove the reverse inclusion, we start with a leftmost derivation
S => al => ao , .. => an = w
G
G
-
G