Convert the following grammar to GNF

S => XA | BB

B => b | SB

X => b

A => a

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014


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

Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More