Solu tion
(i) The given set P does not have any unit productions or
λ-productions.
(ii) None of the given rules is in proper form.
For S
ABa
→
, we have
S
ABB a
→
and
B
a
a →
For A aab
→
, we have
A B B B
a a b
→
and
B
b
b → .
For B
Ac
→ , we have
B
AB c
→
and
B
c
c →
Therefore G 1 has a set of productions ′
P given by
S
ABB
A
B B B
B
AB
B
a
B
b
B
c
a
a a b
c
a
b
c
→
→
→
→
→
→
(iii) In ′
P above, we have
S
ABB
A B B B
a
a a b
→
→
not in proper form.
Hence we assume new variables D 1 and D 2 and the productions
S
AD
D
BB
A
B D
D
B B
a
a
a b
→
→
→
→
1
1
2
2
,
,
,
.
Thus the grammar in Chomsky Normal Form (CNF) is G 2 given by the
productions given by
S
AD
D
BB
A
B D
D
B B
a
a
a b
→
→
→
→
1
1
2
2
,
,
,
,
Con text-free Grammars
145