# Indirect Left recursion

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

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

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)$.