간접적 인 재귀 제거

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

아니오.첫 번째 언어는 비어 있지 않아 (예를 들어, 두 번째 언어가 비어 있지만 두 번째 언어가 비어 있습니다.