Exercício 08.13

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

G = ({S, K, Q, R, T, U, W}, {a, b, c, d, e}, P, S)
P = {< S >  ->  a < K > b < Q >
            |   c d < R >
            |   < U >
     < K > -> < Q > c
            |   < K >
     < Q >  ->  d < K >
            |   c < Q > d c
     < R >  ->  a b < U > < T > d
            |   < U > a b c
            |   a c < T > e
     < T >  ->  < T > a c
            |   c < T > a
            |   a c d
     < U >  ->  a < Q > b < K > c
     < W >  ->  < R > < R > c }

Resposta

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

Conjunto de variáveis que constituem terminais
Iteração Variáveis
0
1 {T}
2 {T, R}
3 {T, R, S, W}
4 {T, R, S, W}
G = ({S, R, T, W}, {a, b, c, d, e}, P, S)
P = {< S >  ->  c d < R >
     < R >  ->  a c < T > e
     < T >  ->  < T > a c
            |   c < T > a
            |   a c d
     < W >  ->  < R > < R > c }

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, R} {c, d}
2 {S, R, T} {c, d, a, e}
3 {S, R, T} {c, d, a, e}
G = ({S, R, T}, {a, c, d, e}, P, S)
P = {< S >  ->  c d < R >
     < R >  ->  a c < T > e
     < T >  ->  < T > a c
            |   c < T > a
            |   a c d }

Recomendamos

Copy Revista FOSSGIS Brasil Clique Alimentos