0
$\begingroup$

I have a grammar: $A\rightarrow Aa|bB|c$

The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to avoid left recursive.

Some body please guide me how to do that.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Consider where "a" terminals can appear in a string produced by this grammar. Based on that, you should be able to split the "A" nonterminal up to make a right-recursive grammar that matches the same strings.

(Also, your "B" nonterminal appears to be missing...? Or just has no productions?)

Improve this answer
$\endgroup$
2
  • $\begingroup$ What we found was : A->bB|c|bBZ|cZ & then Z->a|aZ. Can some body improve this example? $\endgroup$
    – user2994783
    Nov 27, 2019 at 2:52
  • $\begingroup$ @user2994783 Consider whether using an ε production for Z would help (if your definitions allow ε productions for nonterminals other than the start nonterminal). $\endgroup$
    – Aaron Rotenberg
    Nov 27, 2019 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.