192 ~ Theory of Computer Science
*
Theorem 6.1, we can split this as A ~ X]X 2 ... X lIl ~ W(l-V2 ... 'V m such
that X j ~ H} If Xi E L, then Wj = Xj'
. G '
"
If X j E V N then by (i), X j E V~v. As X j ~ Wj in at most k steps,
X j ~ Wj' Also, Xl, X 2 , X lIl E (L U V~v)* implies that A ~ X l X 2 ... X I1l is
in P'. Thus, A ~ XIX~ ... X lIl ::b WlW2 ... Will' Hence by induction, (6.5)
G'
-
G ' .
•
is true for all derivations. In particular, S ~ W implies S => w. This proves
G
G'
that L(G) ~ L(G'), and (ii) is completely proved. I
Theorem 6.4 For every CFG G = (VN, L, P, S), we can construct an
equivalent grammar G' =(V N , L', p', S) such that every symbol in \1"1 U L'
appears in some sentential form (i.e. for every X in V: v U L' there exists a
such that S ::b a and X is a symbol in the string a).
G'
Proof We construct G' = (V'N' L', P', S) as follows:
(a) Construction of Wi for i ?: 1:
(i) WI = IS}.
(ii) W i + l =Wi U {X E \1v U L I there exists a production A ~ a with
A E Wi and a containing the symbol X}.
We may note that Wi ~ v'v uLand Wi ~ W i + l • As we have only a finite
number of elements in V N U L, W k = W k + 1 for some k. This means that
W k = W k + j for all j ?: O.
(b) Construction of V N , L' and p':
We define
V N = Vv ( l W k ,
L' = L U W k
P'= {A ~ alA E W k }.
Before proving that G' is the required grammar, we apply the construction to
an example.
EXAMPLE 6.6
Consider G = ({S, A, B, E}, {a, b, c}, P, S), where P consists of S ~ AB,
A ~ a, B ~ b, E ~ c.
Solution
WI = IS}
W 2 = IS} U {X E \!y U L I there exists a production A ~ a with
A E WI and a containing X}
= IS} U {A, B}