204 J;l Theory of Computer Science
Let W E L(G j ). To show that W E L(G), it 1S enough to prove the
following:
(6.7)
*
We prove (6.7) by induction on the number of steps in A => w.
G,
If A => w, then A ---+ H' is a production in Pl' By construction of Pj, .v is
G,
a single terminal. So A ---+ W is in P, i.e. A => w. Thus there is basis for
induction.
G
Let us assume (6.7) for derivations in at most k steps. Let A ~ w. We can
G,
split this derivation as A => A]A 2 . .. Alii !b W] . W m = W such that Ai ~ Wi'
~
~
~
*
Each Ai is either in Vy or a new variable, say C", When Ai E V N , Ai => Wi
•
1
~
~,'
is a derivation in at most k steps. and so by induction hypothesis, Ai => Wi'
. .
. G
When Ai = C"i' the production CUi ---+ ai is applied to get Ai ::S Wi' The
production A ---+ A j A 2 ... Alii is induced by a production A ---+ X j X 2 .•• XIII
in P where Xi = Ai if Ai E V N and Xi = Wi if Ai = CUI' So A => X j X 2 ... XIII
G
b H'jH'2 . . . Wm' i.e. A b w. Thus, (6.7) is true for all derivations.
G
G
Therefore. L(G) = L(G]).
The effect of applying A ---+ A j A 2 •.. Am in a derivation for W E L(G j )
can be achieved by applying the productions A ---+ A] C l , C l ---+ A 2 C 2 ,
C m - 2 ---+ Am-lAm in P2' Hence it is easy to see that L(G I ) <;;;; L(G 2 ).
To prove L(Gc) <;;;; L(G j ), we can prove an auxiliary result
A=>w
G,
if A E V;v, A => tV
G.
(6.8)
Condition (6.8) can be proved by induction on the number of steps in A => w.
G,
Applying (6.7) to S. we get L(G 2 ) <;;;; L(G). Thus.
L(G) = L(G j ) = L(G 2 ) I
EXAMPLE 6.12
Find a grammar in Chomsky normal form equivalent to S ---+ aAbB, A ---+
aAla. B ---+ bBlb.