Non-Left recursive grammar of the below grammar.

Question

Grammar.

 

S → Aa | B

A → Ac | Aad | bd | epsilon .

 

 .

Comments

S -> Aa / B

A -> bdA' / A'

A' -> cA' / adA' / epsilon

Answer 1

Left recursion is eliminated by converting the grammar into a right recursive grammar.

Consider the grammar with left recursion: $A\rightarrow A\alpha/\beta$

Then we can eliminate left recursion by: $A\rightarrow\beta A’,A’\rightarrow\alpha A’/\epsilon$

Consider the given grammar:

$S\rightarrow Aa/B$

$A\rightarrow Ac/Aad/bd/\epsilon$

After removing the left recursion we get:

$S\rightarrow  Aa / B$

$A \rightarrow bdA' / A'$

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