Exercício 08.47

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

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

Resposta

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

Conjunto de variáveis que constituem terminais
Iteração	Variáveis
0	∅
1	{E}
2	{E, D}
3	{E, D, A}
4	{E, D, A}

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

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