Chapter 6: Context-Free Languages );,J 191
W~ = Wj U {AI E V:vlAj ----t a for some a E (2: U {A, B, E})*}
= tV] u {S} = {A~ B, E, S}
W 3 =W~ U {AI E V:vlAI ----t a for some a E (2: U {S, A, B, E})*}
=W, U 0 = Wo
Therefore,
V N = {S. A. B, F}
(b) Construction of p':
P' = {AI ----t aIA[. a E (V:v U 2:)*}
= {S ----t AB, A ----t a, B ----t b, E ----t c}
Therefore.
G' = ({S, A, B, E}, {a, b. c}, P'. S)
Now we prove:
*
(i) If each A E V',. then A ::S w for some W E 2:*; conversely. if A ~ w,
, ,
G'
G
then A E V v ,
(ii) L(G') = L(G),
To prove (i) we note that W k = WI U W~ ... U Wk' We prove by
induction on i that for i = 1, 2..... k. A E Wi implies A ::S w for some
G'
W E 2:*. If A E W j • then A ~ w. So the production A ----t w is in P'.
G
Therefore. A ::S lV. Thus there is basis for induction. Let us assume the result
G'
for i. Let A E W i + l • Then either A E Wi' in which case. A ::S w for some
G'
w E 2:* by induction hypothesis. Or. there exists a production A ----t a with
a E (2: U wJ*. By definition of P'. A ----t a is in P'. We can write
a =XIX~ ... X m , where X j E 2: U Wi' If X j E Wi by induction hypothesis.
Xl' ::S Wi for some Wi E 2:*. So, A ::S ~1)[W~ ... H' m E 2:* (when XI' is a terminaL
G' '
' G '
,
Wi = Xi)' By induction the result is true for i = 1. 2, ' ... k.
The converse part can be proved in a similar way by induction on the
number of steps in the derivation A ~ w. We see immediately that L(G') k
G
L(G) as V~. k V:v and P' k P, To prove L(G) k L(G'), we need an auxiliary
result
~:
A ::; w
if A ~ w for some lV E 2:*
(6.5)
G'
G
We prove (6.5) by induction on the number of steps in the derivation A ~ W.
G
If 11 ~ w, then A ----t w is in P and A E W] k V'v. As A E V;v and vV E 2:*.
G
A ----t w is in P'. So A ~ w, and there is basis for induction. Assume (6.5)
G'
k+1
for derivations in at most k steps, Let A ~ w. By Remark appeating after
G