Exercício 08.12

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

G = ({S, A, B, C, D, F, H}, {a, b, c, d}, P, S)
P = {< S >  ->  < A > < C > < H >
            |   < B > < B >
     < A >  ->  a < A >
            |   a < F >
     < B >  ->  < C > < F > < H >
            |   b
     < C >  ->  a < C >
            |   < D > < H >
     < D >  ->  a < D >
            |   < B > < D >
            |   < C > a
     < F >  ->  b < B >
            |   b
     < H >  ->  d < H >
            |   d }

Resposta

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

Conjunto de variáveis que constituem terminais
Iteração	Variáveis
0	∅
1	{B, F, H}
2	{B, F, H, S, A}
3	{B, F, H, S, A}

G = ({S, A, B, F, H}, {a, b, c, d}, P, S)
P = {< S >  ->  < B > < B >
     < A >  ->  a < A >
            |   a < F >
     < B >  ->  b
     < F >  ->  b < B >
            |   b
     < H >  ->  d < H >
            |   d }

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, B}	∅
2	{S, B}	{b}

G = ({S, B}, {b}, P, S)
P = {< S >  ->  < B > < B >
     < B >  ->  b }