198 l;l, Theory of Computer Science
W "* A, A ~ W is a production in pI, and so A ::::;> w. Thus there is basis for
G,
induction. Assume the result for derivations in at most i steps. Let A i,g wand
.
G
I
W "* A. We can split the derivation as A ~ XIX~ ... X k 7" WjW~ ... Wk,
.' .
G
where W = 1V1W2 ... Wk and Ai ~ wi' As W "* A, not all ¥I'j'S are A. If wi "* A,
G
then by induction hypothesis, Xi b ¥lj. If ,Vi =A, then Xi E W So using the
. G,
.
production A ~ AjA~ ... A k in P, we construct A ~ al a~ ... ak in P',
where (Xi = Xi if wi "* A and ai = A if wi = A (i.e. Xi E W). Therefore,
A ~ ala~ ... ak ,;, Wja2 ... ak::::;> ... => wlw2 ... Wk = W
~
~
~
By the principle of induction, the 'if' part of (6.6) is proved.
We prove the 'only if' part by induction on the number of steps in the
derivation of A ,;, w. If A ~ w, then A ~ w is in Pj. By construction of P',
G,
G,
A ~ w is obtained from some production A ~ X jX 2 .•• XII in P by erasing
some (or none of the) nullable variables. Hence A ::::;> X 1 X 2 ••• XII ~ W. SO
G
G
there is basis for induction. Assume the result for derivation in at most j steps.
J - r l . .
i
Let A ::::;> W. ThiS can be split as A ~ XjX~ ... X k d WjW2 ... Wh where
G
G,
I
0::
X => Wi' The first production A ~ X j X 2 ... X k in P' is obtained from some
I
G
production A ~ a in P by erasing some (or none of the) nullable variables
,.
0
in a. So A ::::;> u. ~ XjX~ ... X k . If Xi E L then Xi ~ Xi =Wi' If Xi E V N
G
G
G
then by induction hypothesis, Xi ~ Wi' So, we get A 7" Xj X 2 ... X k ~
G
G
WjW~ ... Wk' Hence by the principle of induction whenever A ~ w, we have
G 1
A ~ wand W "* A. Thus (6.6) is completely proved.
G
By applying (6.6) to S. we have W E L(G j ) if and only if W E L(G) and
W "* A. This implies L(G j ) = L(G) - {A}. I
Corollary 1 There exists an algorithm to decide whether A E L(G) for a
given context-free grammar G.
Proof A E L(G) if and only if SEW. i.e. S is nullable. The construction
given in Theorem 6.6 is recursive and terminates in a finite number of steps
(actually in at most IVy I steps). So the required algorithm is as follows:
(i) construct W; (ii) test whether SEW.
W "* A, A ~ W is a production in pI, and so A ::::;> w. Thus there is basis for
G,
induction. Assume the result for derivations in at most i steps. Let A i,g wand
.
G
I
W "* A. We can split the derivation as A ~ XIX~ ... X k 7" WjW~ ... Wk,
.' .
G
where W = 1V1W2 ... Wk and Ai ~ wi' As W "* A, not all ¥I'j'S are A. If wi "* A,
G
then by induction hypothesis, Xi b ¥lj. If ,Vi =A, then Xi E W So using the
. G,
.
production A ~ AjA~ ... A k in P, we construct A ~ al a~ ... ak in P',
where (Xi = Xi if wi "* A and ai = A if wi = A (i.e. Xi E W). Therefore,
A ~ ala~ ... ak ,;, Wja2 ... ak::::;> ... => wlw2 ... Wk = W
~
~
~
By the principle of induction, the 'if' part of (6.6) is proved.
We prove the 'only if' part by induction on the number of steps in the
derivation of A ,;, w. If A ~ w, then A ~ w is in Pj. By construction of P',
G,
G,
A ~ w is obtained from some production A ~ X jX 2 .•• XII in P by erasing
some (or none of the) nullable variables. Hence A ::::;> X 1 X 2 ••• XII ~ W. SO
G
G
there is basis for induction. Assume the result for derivation in at most j steps.
J - r l . .
i
Let A ::::;> W. ThiS can be split as A ~ XjX~ ... X k d WjW2 ... Wh where
G
G,
I
0::
X => Wi' The first production A ~ X j X 2 ... X k in P' is obtained from some
I
G
production A ~ a in P by erasing some (or none of the) nullable variables
,.
0
in a. So A ::::;> u. ~ XjX~ ... X k . If Xi E L then Xi ~ Xi =Wi' If Xi E V N
G
G
G
then by induction hypothesis, Xi ~ Wi' So, we get A 7" Xj X 2 ... X k ~
G
G
WjW~ ... Wk' Hence by the principle of induction whenever A ~ w, we have
G 1
A ~ wand W "* A. Thus (6.6) is completely proved.
G
By applying (6.6) to S. we have W E L(G j ) if and only if W E L(G) and
W "* A. This implies L(G j ) = L(G) - {A}. I
Corollary 1 There exists an algorithm to decide whether A E L(G) for a
given context-free grammar G.
Proof A E L(G) if and only if SEW. i.e. S is nullable. The construction
given in Theorem 6.6 is recursive and terminates in a finite number of steps
(actually in at most IVy I steps). So the required algorithm is as follows:
(i) construct W; (ii) test whether SEW.