Question: Convert the following grammar to GNF
0

S => XA | BB

B => b | SB

X => b

A => a

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi750
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

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi750
Please log in to add an answer.