and
A B AAB
a
b
→
not in proper form.
Hence we assume new variables D 1 , D 2 , D 3 , D 4 and D 5 with
productions given as below:
For S
B B SB
a b
b
→
, we have
S
B D
D
B D
D
SB
a
b
b
→
→
→
1
1
2
2
,
,
For S
B AB
a
b
→
, we have
S
B D
D
AB
a
b
→
→
3
3
For A B AAB
a
b
→
, we have
A
B D
D
AD
D
AB
a
b
→
→
→
4
4
5
5
Therefore, the grammar in Chomsky Normal Form (CNF) is G 2
with production given by
S
B D
D
B D
D
SB
S
B D
D
AB
A
B D
D
AD
D
AB
A
a
b
b
a
b
a
b
→
→
→
→
→
→
→
→
1
1
2
2
3
3
4
4
5
5
→
→
→
B S
B
a
B
b
b
a
b
and
S
a
→ .
Ì Exam ple 2.5.4: Obtain the grammar G given by P as S
a b cSS
→ | |
.
Solu tion
(i) There are no λ-productions and no unit productions in given P.
(ii) Among the given productions,
S
a
→
and
S
b
→
are in proper form.
Con text-free Grammars
147