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 }

Recomendamos

Clique Alimentos Um Sábado Qualquer cert.br