we have $
P for an equivalent grammar given by
S
AB
A a
B
b
→
→
→
Ì Exam ple 2.4.8: Eliminate the unit-production from the CFG with P
given by
S
Aa B
B
A bb
A a bc B
→
→
→
|
|
| | .
Solu tion
From the given P we shall draw the dependency graph as follows.
From this we see that
S A
S B
B A
A B
⇒
⇒
⇒
⇒
*
*
*
*
Therefore these rules are added to the original non-unit productions
S
Aa
A a bc
P
B
bb
→
→
→
|
(from given )
the following new rules
S
a bc bb
A bb
B
a bc
→
→
→
| |
|
in order to obtain
S
a bc bb Aa
A a bb bc
B
a bb bc
→
→
→
| | |
| |
| |
which is $
P for the new gram mar gen er ated equiv a lent to the given gram mar.
140
Theory of Automata, Formal Languages and Computation
S
B
A