Exercício 08.10

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

G = ({S, A, B, C, D}, {0, 1}, P, S)
P = {< S > ::= 0 < S > 1
            |  0 < A >
            |  0 1 < C >
     < A > ::= < A > < S > < C >
            |  1 < C >
            |  1
     < B > ::= 0 < B > 1
            |  0 1
     < C > ::= 0 < D > 1
     < D > ::= 0 1 < C > }

Resposta

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

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

G = ({S, A, B}, {0, 1}, P, S)
P = {< S > ::= 0 < S > 1
            |  0 < A >
     < A > ::= 1
     < B > ::= 0 < B > 1
            |  0 1 }

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, A}	{0, 1}
2	{S, A}	{0, 1}

G = ({S, A}, {0, 1}, P, S)
P = {< S > ::= 0 < S > 1
            |  0 < A >
     < A > ::= 1 }