similar, although more complicated, manner.
Theorem 6.3
Let G be any context-free grammar with λ not in L (G). Then there exists an
equivalent grammar having no λ-productions.
Proof: We first find the set V N of all nullable variables of G, using the following
steps.
1. For all productions A → λ, put A into V N .
2. Repeat the following step until no further variables are added to V N .
For all productions
B → A 1 A 2 …A n ,
where A 1 , A 2 ,…, A n are in V N , put B into V N .
Once the set V N has been found, we are ready to construct . To do so, we look
at all productions in P of the form
where each
. For each such production of P, we put into that
production as well as all those generated by replacing nullable variables with λ
in all possible combinations. For example, if x i and x j are both nullable, there
will be one production in with x i replaced with λ, one in which x j is replaced
with λ, and one in which both x i and x j are replaced with λ. There is one
exception: If all x i are nullable, the production A → λ is not put into .
The argument that this grammar is equivalent to G is straightforward and
will be left to the reader.
Example 6.5
Find a context-free grammar without λ-productions equivalent to the grammar