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.


1 Answer 1


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?)

  • $\begingroup$ What we found was : A->bB|c|bBZ|cZ & then Z->a|aZ. Can some body improve this example? $\endgroup$ 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$ 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.