Chapter 6: Context-Free Languages ~ 197
R.H.S. of A ~ X j X 2 ••• X k or by erasing some or all nullable variables
provided some symbol appears on the R.H.S. after erasing.
Let G j = CV:v, 2.:, pI, S). G] has no null productions.
Before proving that G] is the required grammar, we apply the construction
to an example.
EXAMPLE 6.9
Consider the grammar G whose productions are S ~ as IAS, A ~ A,
S ~ A, D ~ b. Construct a grammar G] without null productions generating
L(G) - {A}.
Solution
Step 1 Construction of the set W of all nullable variables:
W j = {AI E Vv IA j ~ A is a production in G}
= {A, B}
W 2 = {A, B} u {S} as S ~ AB is a production with AS E wt
= {S, A, B}
W 3 = W, U 0= w,
Thus.
W =W 2 = {S, A, B}
Step 2 Construction of pI:
(i) D ~ b is included in pl.
(ii) S ~ as gives rise to S ~ as and S ~ a.
(iii) S ~ AB gives rise to S ~ AB, S ~ A and S ~ B.
(Note: We cannot erase both the nullable variables A and Bin S ~ AB as we
will get S ~ A in that case.)
Hence the required grammar without null productions is
G j = ({S, A, B. D}.{a, b}. P, S)
where pI consists of
D ~ b, S ~ as. S ~ AS, S ~ a, S ~ A, S ~ B
Step 3 L(G j ) = L(G) - {A}. To prove that L(G) = L(G) - {A}, we prove
an auxiliary result given by the following relation:
For all A E Vv and >1,' E 2.:*,
A ~ w if and only if A ~ >1,' and w ~ A
G,
G
(6.6)
We prove the 'if part first. Let A ~ wand Ii' ;f. A. We prove that A ~ w
G
G
by induction on the number of steps in the derivation A ~ w. If A => HI ~nd
G
G