196 ~ Theory of Computer Science
Hence,
p" = {A) ~ cx 1 A j E W 3 }
= {S ~ aAa, A ~ Sb 1 bCC, C ~ abb}
Therefore.
G' = ({S. A, C}, {a. b}, p", S)
is the reduced grammar.
6.3.2 ELIMINATION OF NULL PRODUCTIONS
A context-free grammar may have productions of the form A ~ A. The
production A ~ A is just used to erase A. So a production of the form A ~
A, where A is a variable, is called a null production. In this section we give a
construction to eliminate null productions.
As an example, consider G whose productions are S ~ as I aA 1 A,
A ~ A. We have two null productions S ~ A and A ~ A. We can delete
A ~ A provided \ve erase A whenever it occurs in the course of a derivation
of a terminal string. So we can replace S ~ aA by S ~ a. If G) denotes
the grammar whose productions are S ~ as 1 a 1 A, then L( G j ) = L(G) =
{a" 1 n ~ O}. Thus it is possible to eliminate the null production A ~ A. If
we eliminate S ~ A, we cannot generate A in L(G). But we can generate
L(G) - {A} even if we eliminate S ~ A.
Before giving the construction we give a definition.
DefInition 6.9 A variable A in a context-free grammar is nullable if A ~ A.
Theorem 6.6 If G = (~v, L, P. S) is a context-free grammar, then we can
find a context-free grammar G j having no null prodctions such that L(G) =
L(G) - {A}.
Proof We construct G j = (Vv, L, p', S) as follows:
Step 1 Construction of the set of nltllable variables:
We find the nullable variables recursively:
(i) W) = {A E Vv 1 A ~ A is in P}
(ii) W i + j = Wi U {A E Vv Ithere exists a production A ~ CX with cx E W i *}.
By definition of Wi' Wi k W i +) for all i. As ~v is finite. W k + 1 = W k for some
k ::; 1~v I· SO, W k + j = W k for all j. Let VV = Wk' W is the set of all nullable
variables.
Step 2 (i) Construction of p':
Any production whose R.H.S. does not have any nullable variable is included
in p'.
(ii) If A ~ X j X 2 ... X k is in P, the productions of the form A ~ CXjCX2
CXk are included in p', where CXj = Xi if Xi €O W. CXi = X, or A if X, E
Wand CX1CX2 ... CXk 7:- A. Actually, (ii) gives several productions in P~ The
productions are obtained either by not erasing any nullable vmiable on the
Hence,
p" = {A) ~ cx 1 A j E W 3 }
= {S ~ aAa, A ~ Sb 1 bCC, C ~ abb}
Therefore.
G' = ({S. A, C}, {a. b}, p", S)
is the reduced grammar.
6.3.2 ELIMINATION OF NULL PRODUCTIONS
A context-free grammar may have productions of the form A ~ A. The
production A ~ A is just used to erase A. So a production of the form A ~
A, where A is a variable, is called a null production. In this section we give a
construction to eliminate null productions.
As an example, consider G whose productions are S ~ as I aA 1 A,
A ~ A. We have two null productions S ~ A and A ~ A. We can delete
A ~ A provided \ve erase A whenever it occurs in the course of a derivation
of a terminal string. So we can replace S ~ aA by S ~ a. If G) denotes
the grammar whose productions are S ~ as 1 a 1 A, then L( G j ) = L(G) =
{a" 1 n ~ O}. Thus it is possible to eliminate the null production A ~ A. If
we eliminate S ~ A, we cannot generate A in L(G). But we can generate
L(G) - {A} even if we eliminate S ~ A.
Before giving the construction we give a definition.
DefInition 6.9 A variable A in a context-free grammar is nullable if A ~ A.
Theorem 6.6 If G = (~v, L, P. S) is a context-free grammar, then we can
find a context-free grammar G j having no null prodctions such that L(G) =
L(G) - {A}.
Proof We construct G j = (Vv, L, p', S) as follows:
Step 1 Construction of the set of nltllable variables:
We find the nullable variables recursively:
(i) W) = {A E Vv 1 A ~ A is in P}
(ii) W i + j = Wi U {A E Vv Ithere exists a production A ~ CX with cx E W i *}.
By definition of Wi' Wi k W i +) for all i. As ~v is finite. W k + 1 = W k for some
k ::; 1~v I· SO, W k + j = W k for all j. Let VV = Wk' W is the set of all nullable
variables.
Step 2 (i) Construction of p':
Any production whose R.H.S. does not have any nullable variable is included
in p'.
(ii) If A ~ X j X 2 ... X k is in P, the productions of the form A ~ CXjCX2
CXk are included in p', where CXj = Xi if Xi €O W. CXi = X, or A if X, E
Wand CX1CX2 ... CXk 7:- A. Actually, (ii) gives several productions in P~ The
productions are obtained either by not erasing any nullable vmiable on the