B
AB
B
a
B
b
c
a
b
→
→
→
,
,
,
and
B
c
c → .
Ì Exam ple 2.5.3: Reduce the given CFG with P given by
S
abSb a aAb
→
| |
and A bS aAAb
→
|
to Chomsky Normal Form (CNF).
Solu tion
(i) There are neither λ-productions nor unit product in the given set of
P.
(ii) Among the given productions, we have
S
a
→
in proper form.
For S
abSb
→
, we have
S
B B SB
a b
b
→
, B
a
a → , and B
b
b → .
For S
aAb
→
, we have
S
B AB
a
b
→
.
For A bS
→ , we have
A B S
b
→
.
For A aAAb
→
, we have
A B AAB
a
b
→
.
Therefore, we have G 1 given by
G
S A B B
a b P S
a
b
1 =
′
({ , , , }, { , }, , )
which has P′ given by
S
B B SB
S
B AB
A
B AAB
A
B S
B
a
B
b
a b
b
a
b
a
b
b
a
b
→
→
→
→
→
→
and
S
a
→ .
(iii) In P′ above, we have
S
B B SB
S
B AB
a b
b
a
b
→
→
146
Theory of Automata, Formal Languages and Computation