Exercício 08.15

Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática:

G = ({S, R, X, Z, W, Y, K, T}, {a, b, c}, P, S)
P = {< S >  ->  < W > b
            |   b < T >
     < R >  ->  < X > b b < A >
            |   < Y > a < Z > b
     < X >  ->  < K >  c
            |   a < W > b
     < Z >  ->  c
            |   < A > b
            |   c < W > b
     < W >  ->  a b < X >
            |   < K > < A > c
     < Y >  ->  < A > < Z > c
            |   < K > a < X >
     < K >  ->  < X > < R >
            |   < W > < A >
     < T >  ->  < S >
            |   < T > a
            |   < K > < X >
            |   a }

Resposta

a) Identificação das variáveis que constituem terminais

Conjunto de variáveis que constituem terminais
Iteração	Variáveis
0	∅
1	{Z, T}
2	{Z, T, S}
3	{Z, T, S}

G = ({S, Z, T}, {a, b, c}, P, S)
P = {< S >  ->  b < T >
     < Z >  ->  c
     < T >  ->  < S >
            |   < T > a
            |   a }

b) Identificação dos símbolos alcançáveis a partir do símbolo inicial

Conjunto de símbolos alcançáveis a partir do símbolo inicial
Iteração	Variáveis	Terminais
0	{S}	∅
1	{S, T}	{b}
2	{S, T}	{b, a}

G = ({S, T}, {a, b}, P, S)
P = {< S >  ->  b < T >
     < T >  ->  < S >
            |   < T > a
            |   a }