Solu tion
A a B
b E
a
→
→
→
,
,
are nonunit production. Therefore $
P will contain these
productions.
Since B E
⇒
*
, and E a
→ is a non-unit production, include B
a
→ in $
P.
Since C E D E
⇒
⇒
*
,
, include C
a D a
→
→
,
in $
P.
Hence we have the equivalent grammar without unit productions as $
G
defined by
$ ({ , , , , , }, { , }, $ , )
G
S A B C D E a b P S
=
with $
P given by
S
AB
A a
B
b
B
a
C
a
D a
→
→
→
→
→
→
Ì Exam ple 2.4.7: Given a CFG with P given by
S
AB
A a
B C
C
D
D b
→
→
→
→
→ .
Eliminate the unit productions to obtain an equivalent grammar.
Solu tion
In the grammar defined by P, we have
B C
C
D
→
→
as unit-pro duc tions.
We can replace
B C
C
D
→
→
and
D b
→
by
B
b
→ ,
Con text-free Grammars
139