Therefore, we have G 1 given by
G
S A B B B
a b P S
a
b
1 =
′
({ , , , , }, { , }, , )
where P′ has the productions
S
B AB B
A
B A
B
B B
B
a
B
b
A
a
B
b
a
b
a
b
a
b
→
→
→
→
→
→
→
(iii) In P′ above, we have only
S
B AB B
a
b
→
not in proper form.
Hence we assume new variables D 1 and D 2 and the productions
S
B D
D
AD
D
B B
a
b
→
→
→
1
1
2
2
Therefore the grammar in Chomsky Normal Form (CNF) is G 2 with the
productions given by
S
B D
D
AD
D
B B
A
B A
B
B B
B
a
B
b
A
a
a
b
a
b
a
b
→
→
→
→
→
→
→
→
1
1
2
2
,
,
,
,
,
,
,
,
and
B
b
→ .
Ì Exam ple 2.5.2: Obtain a grammar in Chomsky Normal Form (CNF)
equivalent to the grammar G with productions P given by
S
ABa
A aab
B
AC
→
→
→
144
Theory of Automata, Formal Languages and Computation