removing indirect left recursion

Question

I want to remove indirect left recursion from these rules:

    S-->TU,
    T-->US|b,
    U-->ST|a

I don't know if I can implement the algorithm correctly. My assumption is to make it like this:

S-->TU, T-->U'b, U'b-->U'a

Is this correct?

Answer 1

It's tedious... I hope I didn't make a mistake...

S->TU
T->US|b
U->ST|a

1.
S->TU
T->U(TU)|b 
U->(TU)T|a

2.
S->TU
T->aTU|(TUT)TU|b 
U->bUT|(UTU)UT|a

3. * is regex for "repeated 0 or more times"
S->TU
T->aTU|T(UTTU)*|b 
U->bUT|U(TUUT)*|a

4.
S->TU
T->aTU|aTUX|bX|b 
U->bUT|bUTY|aY|a

X->UTTUX|UTTU
Y->TUUTY|TUUT

By substitution of all possibilities of T and U you can remove the non-Terminals at the front of the expressions for X, Y and S.

Answer 2

No. The first language is non empty (e.g., it contains the word "ba"), while the second language is empty.