I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol.

S -> Aa / a   eq1
A -> Sb / b.  eq2

Now I can do this in two ways. First is :

Putting A in eq1

So I'll get the solution (sol1):

S-> Sba /a /ba

and then

S -> aS' / baS'

S' -> baS' / epsilon

Then another method is :

Replacing S in eq2 So I'll get the solution (sol2):

S -> Aa / a

A -> abA' / bA'

A' -> abA' / epsilon

Now which is the correct answer because both seems to be correct?.

  • 1
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Feb 6 '16 at 17:00

Yes, both your answers are correct. Note that the language under consideration is regular, see wikipedia.

The first grammar is equivalent to this regular expression: $$r_1 = a(ba)^* \mid (ba)^+.$$

The second grammar is equivalent to this regular expression: $$r_2 = (ab)^+a \mid b(ab)^*a \mid a.$$

It's easy to prove those regexes generate equal languages $L(r_1) = L(r_2)$.


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.