Exercício 08.14

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

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

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, X}
4	{Z, T, S, X, W}
5	{Z, T, S, X, W, Y}
6	{Z, T, S, X, W, Y}

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

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	{X}	∅
1	{X, S, Z}	∅
2	{X, S, Z}	{a, b}

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