2
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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