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 $A_i =\gtA_j$, ensure that i<=j

If the condition cannot be handled , it can be replaced with the terminal to convert it to GNF directly

Here, $A_3 =\gtA_2A_2$ does‟nt follow the rule i<=j

So,

$A_3 =\gtaA_2$ which is now in GNF(Substituting$ A_2 =\gta)$

Step 3: Remove Left Recursion

Here, left recursion occurs in $A_2 =\gtA_2A_3|a$

We use another variable $B_2$ which holds the RHS of the production causing left recursion and $A_2$ holds the other productions of itself that donot cause left recursion

So,

$A_2 =\gta$

$B_2 =\gtA_2A_3$

Now, we append the new variable(B2) to both the production rules

$A_2 =\gta|aB_2$

$B_2 =\gtA_2A_3| A_2A_3B_2$

Which has no left recursion anymore

Step4: Convert all production rules to GNF

$A_2 =\gta|aB_2$ which is GNF

Consider $B_2 =\gtA_2A_3| A_2A_3B_2$

Substituting $A_2 =\gta$, we get

$B_2 =\gtaA_3| aA_3B_2$ which is GNF

Consider $A_1 =\gt A_2A_3|A_3A_4$

Substituting $A_2 =\gta and A_3 =\gtb$, we get

$A_1 =\gt aA_3|bA_4$which is GNF

$A_4 =\gta|b$is a GNF

Consider $A_3 =\gt A_2A_2| A_4A_3|b$

Substituting $A_2 =\gta and A_4 =\gta$, we get

$A_3 =\gt aA_2| aA_3|b$ which is GNF.