# Indirect Left recursion

I'm resolving indirect left recursion for these production rules:

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


Where S is the starting symbol.

Now I can do this in two ways:

1. Putting A in eq1

So I'll get the solution (sol1):

S -> Sba /a /ba


and then

S -> aS' / baS'
S' -> baS' / epsilon

2. Replacing S in eq2:

So I'll get the solution (sol2):

S -> Aa / a
A -> abA' / bA'
A' -> abA' / epsilon


Both seem to be correct. Which is the correct answer?

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