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$
  • 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 Feb 6 '16 at 17:00
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)$.

| cite | improve this answer | |
$\endgroup$

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.