Elimine a recursividade à esquerda, desconsiderando a palavra vazia, das produções da gramática a seguir.
G = ({S, X, K, Y}, {x, y, z}, P, S)
P = {S → KY | XK
X → XK | x
K → YK | XX | x
Y → y | z}
1. Simplificação da gramática livre de contexto:
G = ({S, X, K, Y}, {x, y, z}, P, S)
P = {S → KY | XK
X → XK | x
K → YK | XX | x
Y → y | z}
2. Renomeação das variáveis em uma ordem crescente qualquer:
G = ({A, B, C, D}, {x, y, z}, P, A)
P = {A → CD | BC
B → BC | x
C → DC | BB | x
D → y | z}
4. Exclusão das recursões da forma Ar → Arα:
G = ({A, B, B1, C, D}, {x, y, z}, P, A)
P = {A → CD | BC
B → xB1 | x
B1 → CB1 | C
C → DC | BB | x
D → y | z}
3. Transformação das produções da forma Ar → Asα, onde r ≤ s:
G = ({A, B, B1, C, D}, {x, y, z}, P, A)
P = {A → CD | BC
B → xB1 | x
B1 → CB1 | C
C → DC | xB1B | xB | x
D → y | z}