Chapter 6: Context-Free Languages );I, 193
W 3 = is, A, B} u {a, b}
W 4 = W 3
V;v= is, A, B}
2:' = {a, b}
P'= {S ~ AB, A ~ a. B~ b}
Thus the required grammar is G' = (V iY , 2:', pI, S).
To complete the proof, we have to show that (i) every symbol in V N U
2:' appears in some sentential form of G', and (ii) conversely. L(G') =L(G).
To prove (i), consider X E V'v U 2:' = W b By construction W k = WI U
W 2 ... U Wk' We prove that X E WI, i ::; k, appears in some sentential fOlm
by induction on i. When i = 1, X = Sand S ~ S. Thus, there is basis for
induction. Assume the result for all variables in Wi' Let X E W i + 1 • Then either
X E Wi, in which case. X appears in some sentential form by induction
hypothesis. Otherwise, there exists a production A ~ 0:, where A E Wi and
0: contains the symbol Xi' The A appears in some sentential form, say f3A y.
Therefore.
5 => f3A Y => f3o:Y
c'
c'
This means that f3o:y is some sentential form and X is a symbol in f30:y. Thus
by induction the result is true for X E Wi, i ::; k.
Conversely, if X appears in some sentential form, say f3Xy. then 2: -:b f3Xy.
This implies X E WI' If I ::; k, then WI ~ W k - If I > k, then WI = W k - cHence
X appears in F;y U 2:'. This proves (i).
To prove (ii), we note L(G') ~ L(G) as V~. ~ ,"",v, 2:' ~ 2: and pI ~ P.
Let ,v be in L(G) and 5 = 0: 1 => 0:2 => 0:3 = ... ~ 0:,,_1 => w. We prove
c
c
c
that every symbol in 0: 1 + 1 is in W i + 1 and O:i => O:i+l by induction on i.
0: 1 = S =? 0:2 implies 5 ~ 0:2 is a production inc'P' By construction, every
C
symbol in 0:, is in W, and S ~ 0:, is in p', i.e. S =? 0:,. Thus, there is basis
-
-
-
c' -
for induction. Let us assume the result for i. Consider O:i+l =? 0: 1 +2' This onestep derivation can be written in the form
c
f31+1 A Yi+l ~ f31+JO:Yi+l
where A ~ 0: is the production we are applying. By induction hypothesis,
A E W i + 1 . By construction of W I + 2 , every symbol in 0: is in W I + 2 . As all the
symbols in f3i+J and Yi+l are also in W I + 1 by induction hypothesis, every symbol
in f31+ 1O:Yi+l = 0: 1 +2 is ill W i + 2 . By the construction of pI, A ~ 0: is in p~
This means that 0:1+1 =? 0:1+2' Thus the induction procedure is complete.
C'
SO 5 = 0: 1 =? 0:, =? 0:3 ~ ... 0:,,_1 =? w. Therefore, W E L(G'). This
c' - c'
G'
c'
proves (ii).