Exercício 08.52

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, d}, P, X)
P = {< X >  ->  a < K > < T >
            |   < Z > < X >
     < Y >  ->  < R > d < S >
            |   a < W >
     < Z >  ->  a b c
            |   < R > d < K >
     < K >  ->  a < K > b
            |   d < R > c
     < W >  ->  < Z > < X >
            |   < K > c b < X >
     < T >  ->  d
            |   < K > < W > b
     < R >  ->  < K > < X > c
            |   d b
     < S >  ->  a < Z >
            |   b < Z >
            |   c < Z >
            |   d < 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, R}
2 {Z, T, R, K, S}
3 {Z, T, R, K, S, X, Y}
4 {Z, T, R, K, S, X, Y, W}
5 {Z, T, R, K, S, X, Y, W}
G = ({X, Y, Z, K, W, T, R, S}, {a, b, c, d}, P, X)
P = {< X >  ->  a < K > < T >
            |   < Z > < X >
     < Y >  ->  < R > d < S >
            |   a < W >
     < Z >  ->  a b c
            |   < R > d < K >
     < K >  ->  a < K > b
            |   d < R > c
     < W >  ->  < Z > < X >
            |   < K > c b < X >
     < T >  ->  d
            |   < K > < W > b
     < R >  ->  < K > < X > c
            |   d b
     < S >  ->  a < Z >
            |   b < Z >
            |   c < Z >
            |   d < 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, K, T, Z} {a}
2 {X, K, T, Z, R, W} {a, b, c, d}
3 {X, K, T, Z, R, W} {a, b, c, d}
G = ({X, Z, K, W, T, R}, {a, b, c, d}, P, X)
P = {< X >  ->  a < K > < T >
            |   < Z > < X >
     < Z >  ->  a b c
            |   < R > d < K >
     < K >  ->  a < K > b
            |   d < R > c
     < W >  ->  < Z > < X >
            |   < K > c b < X >
     < T >  ->  d
            |   < K > < W > b
     < R >  ->  < K > < X > c
            |   d b  }

Recomendamos

Clique Alimentos Clickarvore Kinghost