Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 10M

S => bA|aB

A => bAA|aS|a

B =>aBB|bS|b

For CNF, A => BC(two nonterminals)

Or

A => a(one terminal)

Consider S => bA

S => BA which is a CNF (substituting B =>b)

Consider S => aB

S => AB which is CNF(substituting A => a)

Consider A =>aS

Let $C_1 =\gt a$

$A =\gt C_1S$ which is CNF

Consider A => bAA

A => BAA (substituting B =>b)

Let $C_2 =\gt BA$

$A =\gt C_2A$ which is CNF

Consider B => bS

Let $C_3 =\gt b$

$B =\gt C_3S$ which is CNF

Consider B =>aBB

B =>ABB(Substituting A =>a)

Let $C_4$ =>AB

B => $C_4B$ which is CNF