Ì Exam ple 2.4.9: Given a CFG with P given by
S
AB a
A b
→
→
|
Eliminate the useless symbols to obtain an equivalent grammar.
Solu tion
Given
S
AB a
A b
→
→
|
B is a non-generating symbol. a and b generate themselves. S generates a and A
generates b.
When B is eliminated, S
AB
→
is eliminated. Therefore we have
S a
A b
→
→
S and a are only reachable from S. Therefore we eliminate A and b, therefore
we have
S a
→
as the new $
P for equivalent grammar.
Ì Exam ple 2.4.10: Given the CFG with P given by
S
AB
A aAA
B
bBB
→
→
→
|
| .
λ
λ
Eliminate the λ-productions to obtain $
P for an equivalent CFG.
Solu tion
A and B are “Nullable Symbols” as they have λ-productions. S is also
“Nullable”, because it has the production S
AB
→
, which has only “Nullable
symbols”, A and B.
For S
AB
→
, we have three ways viz.,
S
AB A B
→
| |
For A aAA
→
, we have four ways viz.,
A aAA aA aA a
→
| | |
For B
bBB
→
, we have three ways viz.,
B
bBB bB b
→
| |
Con text-free Grammars
141