Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 10M

Convert the following CFG to GNF:

S => AB|BC

A => AB|a

B => AA|CB|b

C => a|b

For GNF,A =>aα where α can be any value including ε

Step 1: Rename variables

Let S be $A_1,A be A_2, B be A_3 and C be A_4$

Therefore, the grammar now changes to

$A_1 =\gt A_2A_3|A_3A_4$

$A_2 =\gt A_2A_3|a$

$A_3 =\gt A_2A_2| A_4A_3|b$

$A_4 =\gta|b$

Step 2: For each …