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 }