間接左の再帰を削除します

Question

これらの規則から間接左の再帰を削除したい：

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

.

アルゴリズムを正しく実装できるかどうかわかりません。私の仮定はそれをこのようにすることです：

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

.

これは正しいですか？

Answer 1

それは面倒です...私は間違えなかったことを願っています...

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

.

Tとuのすべての可能性を代入することによって、x、y、sの表面の非端子を取り外すことができます。

Answer 2

いいえ。第1の言語は空ではない（例えば、それに単語「BA」を含む）、第2言語は空である。