0
Convert the following grammar to GNF

## A => a

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

0

Step 1: Rename variables

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

Therefore, the grammar now becomes

$A_1 =\gt A_2A_3 \ | \ A_4A_4$

$A_4 =\gt b \ | \ A_1A_4$

$A_2 =\gt b$

$A_3 =\gt a$

Step 2 : For each $A_i =\gt A_j$, ensure i <= j

This is not satisfied by $A_4 =\gt A_1A_4$

Replace $A_1 =\gt A_4A_4$

Hence, we get

$A_4 =\gt A_4A_4 A_4 | b$

Step 3: Remove left recursion, which is not satisfied by $A_4 =\gt A_4A_4 A_4$

Let $B_4 =\gt A_4A_4 A_4 \ | \ A_4A_4 A_4B_4$

Therefore, we get

$A_4 =\gt bB_4$

So left recursion has been removed

Step 4: Get all productions into GNF

Consider $B_4 =\gt A_4A_4 A_4 \ | \ A_4A_4 A_4B_4$

Replacing $A_4 =\gt bB_4$ , which is already in GNF, we get

$B_4 =\gt bB_4 A_4A_4 A_4 \ | \ bB_4A_4A_4B_4$, which is now in GNF

The remaining productions are already in GNF