Chapter 6: Context-Free Languages ~ 207
Let Z be a new variable. Let G 1 = (Vv u {ZL l:, PI' S), where PI is defined
as follows:
(i) The set of A-productions in PI are A ~ f3! I f321 ... !f3s
A ~ f31 Z If32 Z I ... lf3sZ
(ii) The set of Z-productions in PI are Z ~ a1 la2! ... !a r
Z ~ a1Z I a2Z ... !a,Z
(iii) The productions for the other variables are as in P. Then G! is a CFO
and equivalent to G.
Proof To prove L(G) ~ L(G), consider a leftmost derivation of H' in G. The
only productions in P - PI are A ~ AaI! Aa2 ... IA a,. If A ~ Aail'
A ~ Aa i2 , ..., A ~ Aah are used, then A ~ f3j should be used at a later
stage (to eliminate A). So we have A %f 3;Aail ... ail while deriving w in
G. However.
.
l.e.
.
A => f3jAail ... ai;
G]
Thus. A can be eliminated by using productions in G l . Therefore, w E L(G!).
To prove L(G)) ~ UG). consider a leftmost derivation of lV in G!. The
only productions in PI - P are A ~ f3 1 ZI f32ZI ... lf3 s Z. Z ~ all· .. la"
Z ~ ajZ Ia2Z I ... Ia,z. If the new variable Z appears in the course of the
derivation of 11', it is because of the application of A ~ f3 j Z in some earlier
step. Also. Z can be eliminated only by a production of the form Z ~ ~ or
*
Z ~ aJZ for some i and j in a later step. So we get A => f3J·ai ai ... ai
.
1 2 k
~]
in the course of the derivation of w. But, we know that A => f3P i l ai2 ... ai k
'
e
Therefore. W E L(G).
EXAMPLE 6.14
Apply Lemma 6.2 to the following A-productions in a context-free grammar
G.
A ~ aBD IbDB Ie
A ~ ABIAD
Solution
In tL . .; example. al = B. a2 = D, f31 = aBD. f32 = bDB, f33 = c. So the new
productions are:
(i) A ~ aBDlbDBlc.
(ii) Z ~ B, Z ~ D.
A ~ aBDZI bDBZI cZ
Z ~ BZIDZ