B
a
a → . Let V N
′ be the set of variables in V N together with ′
B s
a introduced for
every terminal on RHS.
The resulting grammar G
V V P S
N
T
1 = ′
′
( , , , ) is equivalent to G and every
production in P′ has either a single terminal or two or more variables.
For step (iii): Consider A B B
B m
→ 1 2 KK
where B i ’s are variables and m ≥ 3.
If m = 2, then A B B
→ 1 2
,
is in proper form.
The production A B B
B m
→ 1 2 KK
is replaced by new productions
A
B D
D
B D
D
B B
m
m
m
→
→
→
−
−
1 1
1
2 2
2
1
,
,
LL L L
LL L L
where ′
D S
i are new variables.
The grammar thus obtained is G 2 , which is in CNF.
Ì Exam ple 2.5.1: Obtain a grammar in Chomsky Normal Form (CNF)
equivalent to the grammar G with productions P given
S
aAbB
A aA a
B
bB b
→
→
→
|
| .
Solu tion
(i) There are no unit productions in the given set of P.
(ii) Amongst the given productions, we have
A a
B
b
→
→
,
which are in proper form.
For S
aAbB
→
, we have
S
B AB B
B
a
B
b
a
b
a
b
→
→
→
,
.
For A aA
→ , we have
A B A
a
→
For B
bB
→ , we have
B
B B
b
→
.
Con text-free Grammars
143