Exercício 08.11

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

G = ({A, B, C, D, E, F, G}, {x, y, z}, P, A)
P = {< A >  ->  x < F > y
            |   < B > x < E >
     < B >  ->  x < G >
            |   < G > y
     < C >  ->  y
            |   y < G >
     < D >  ->  z < C >
            |   z z < B >
     < E >  ->  y
            |   < F > x
     < F >  ->  < G > y
            |   < E > x x
     < G >  ->  < B > z < B > }

Resposta

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

Conjunto de variáveis que constituem terminais
Iteração Variáveis
0
1 {C, E}
2 {C, E, D, F}
3 {C, E, D, F, A}
4 {C, E, D, F, A}
G = ({A, C, D, E, F}, {x, y, z}, P, A)
P = {< A >  ->  x < F > y
     < C >  ->  y
     < D >  ->  z < C >
     < E >  ->  y
            |   < F > x
     < F >  ->  < E > x x }

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 {A}
1 {A, F} {x, y}
2 {A, F, E} {x, y}
3 {A, F, E} {x, y}
G = ({A, E, F}, {x, y}, P, A)
P = {< A >  ->  x < F > y
     < E >  ->  y
            |   < F > x
     < F >  ->  < E > x x }

Recomendamos

Revista Espírito Livre Clickarvore Revista Digital