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.

$\endgroup$
0
$\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?)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What we found was : A->bB|c|bBZ|cZ & then Z->a|aZ. Can some body improve this example? $\endgroup$ – user2994783 Nov 27 '19 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 '19 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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