Mathematical Foundation of Computer Science

DHARM

310 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

A → aB [then replace a by Xa] s.t.

(+) Xa → a

So, A → XaB, and

Xa → a are in CNF.

n If both symbols are non terminals then production is in CNF.

n If b has more than two non terminals then replace all non terminals except first

by a new non terminal viz.

A → BCD [then replace CD by R (a new non terminal] s.t.

(+) R → CD

Hence, productions are

A → BR

R → CD are in CNF

n Or, in general if

A → A 1 A 2 A 3 ......AK [then replace A 2 A 3 ...AK by B 1 ] s.t.

(+) B 1 → A 2 A 3 ......AK

Hence, productions becomes

A → A 1 B 1 [is in CNF]

B 1 → A 2 B 2 [where B 2 is replacement of A 3 ......AK] s.t.

(+) B 2 → A 3 ......AK

Hence, production becomes

A → A 1 B 1

B 1 → A 2 B 2 [where B 2 is replacement of A 3 ......AK] s.t.

B 2 → A 3 B 3 [and so on]

..... ....

..... ....

BK–2 → AK–1AK

In this way we can convert all productions into the CNF productions.

Example 11.28. A CFG G is given, convert it to CNF.
S → aB | bA
A → aS | a | bAA
B → bS | b | aBB
Sol. l First, we simplify the grammar and find that grammar is in simplified form Next, we
see that the productions A → a & B → b are in desired form of CNF. Now, replace a by
Xa and b by Xb through adding the productions i.e.
Xa → a and Xb → b
Thus the grammar becomes
S → XaB | XbA
A → XaS | a | XbAA
B → XbS | b | XaBB