{
:
}
a b n
n n
≥1
The λ-pro duc tion in P viz.,
S 1 → λ
is removed after adding new productions by substituting λ for S 1 where it
occurs on the right. Hence we get
S
aS b ab
S
aS b ab
→
→
1
1
1
|
|
which is the new set of P that produces the same language given by
{
:
}
a b n
n n
≥ 1 .
Ì Exam ple 2.4.5: Determine a CFG without λ-production equivalent to
the grammar given by P as
S
ABaC A BC B
b
C
D
D d
→
→
→
→
→
,
,
| ,
| ,
λ
λ
Solu tion
Refer to the procedure outlined in section 2.4.2 to find CFG without
λ-productions.
Step 1: The “Nullable variables” are A, B and C.
Step 2:
S
ABaC BaC ABa AaC Aa Ba ac a
A B C BC
B
b
C
D
D d
→
→
→
→
→
|
|
|
| | | |
| |
The above set of rules represent P′ for the new CFG after elimination of
λ-productions.
Ì Exam ple 2.4.6: Eliminate unit productions from the grammar G given
by productions (P).
S
AB
A a
B C b
C
D
D E
E
a
→
→
→
→
→
→
|
.
138
Theory of Automata, Formal Languages and Computation