Let G be any CFG with λ not in L(G). Then there exists an equivalent
grammar $
G having no λ-productions.
Pro ce dure to find CFG with out λ-Pro duc tions
Step (i): For all productions A → λ, put A into V N .
Step (ii): Repeat the following steps until no further variables are added to V N .
For all productions
B
A A
A n
→ 1 2 KK .
where A A A
A n
1
2
3
, , ,
,
KK
are in V N , put B into V N .
To find $
P, let us consider all productions in P of the form
A x x
x m
m
→
≥
1 2
1
KK ,
for each x V T
i ∈ ∪ .
For each such production of P, we put into $
P that production as well as
all those generated by replacing nullable variables with λ in all possible
combinations.
(If all x i are nullable, the pro duc tion A → λ is not put into $
P).
Let us illustrate this procedure through an example as shown in example
2.4.5.
(b) Unit Pro duc tions Removal
Any production of a CFG of the form
A B
→
where A B V
, ∈ is called a “Unit-production”. Having variable one on either
side of a production is sometimes undesirable.
“Substitution Rule” is made use of in removing the unit-productions.
Given G = (V, T, S, P), a CFG with no λ-productions, there exists a CFG
$ ( $ , $ , , $ )
G V T S P
=
that does not have any unit-productions and that is equivalent
to G.
Let us illustrate the procedure to remove unit-production through example
2.4.6.
Pro ce dure to remove the unit pro duc tions:
Find all variables B, for each A such that
A B
⇒
*
This is done by sketching a “depending graph” with an edge (C, D)
134
Theory of Automata, Formal Languages and Computation