1
$\begingroup$

I have to transform the following grammar into a non left recursive grammar:

S → aSb | bAS

A → AaA | bAA | AAa | bAb

This is what I came up with:

A → bAAA’| bAbA’

A’ → aAA’| AaA’| ε

S → aSb | bAS

As far as I can tell, there is no more left recursion because none of the leftmost symbols on the RHS are the same as the nonterminal on the left. However, assuming S is the starting symbol, there is still infinite recursion because A calls itself repeatedly. Is this expected? Or did I derive the non left recursive grammar incorrectly?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Can you double check the original problem? Can you edit the question to add a reference to the source of the original problem? $\endgroup$ – John L. Feb 23 '19 at 0:38
0
$\begingroup$

Take a look at the following rule in the original grammar.
$\quad S \to aSb \mid bAS$
If you start generation from $S$, you cannot get rid of $S$.
$\quad A \to AaA \mid bAA \mid AAa \mid bAb $
If you continue applying production rules from a sentential form that contains $A$, you cannot get rid of $A$, either.

These rules are called unproductive rules. Unproductive rules and unreachable rules are called useless rules. You may take a look at this question.

If there are useless rules in the original grammar, there will be useless rules after the transformation by pure left-recursion removal procedure. That is why you see "there is still infinite recursion because $A$ calls itself repeatedly". There is nothing wrong with your transformation to that non-left-recursive grammar.

Those useless production rules can be remove by some algorithms. We can see that the original grammar in the question will become empty after such cleaning. Indeed, the original grammar generates the empty language, the language that contains no words.

$\endgroup$
  • $\begingroup$ Thanks for clarifying! I learned something new. $\endgroup$ – Nick Heiting Feb 23 '19 at 2:01
  • $\begingroup$ Welcome! Glad to be helpful. $\endgroup$ – John L. Feb 23 '19 at 2:02

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.