Made Easy Test Series-2016

Question

Ex. Consider the following grammar G.
A → A + B|B
B → int|(A)

Which of the following grammar is equivalent to the above grammar G?

a. A -> int + B | B

    B -> int | (A) | epsilon

b.  A -> BA'

     A' -> BA' | epsilon

     B -> int | (+A)

c. A -> BA'

    A' -> +BA' | epsilon

    B -> int | (A)

d. None of these

 

Solution:

Its clear that we can remove left recursion first then our grammar g becomes,

 A -> BA'

A' -> (A + B)A' | epsilon

B -> int | (A)

but the answer given is C so can anybody please tell me how A' -> (A + B)A' | epsilon becomes    A' -> +BA' | epsilon ?

Answer 1

A → A + B|B
B → int|(A).

the grammar is left recursive,so remove left reursion from that grammar.

removing left recursion from grammar is $A\rightarrow Ac |B$

eliminating left recursion is $A\rightarrow BA' $

                                       $ A'\rightarrow cA' /\epsilon$.

apply left recursion we get:

$A\rightarrow BA'$

$ A'\rightarrow+BA' | \epsilon$

$B\rightarrow int/(A)$

Option (C) is correct.