Exercício 08.27

Converta para a Forma Normal de Chomsky a gramática:

G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
     < X >  ->  < A > < X > < A >
            |   < B > < X > < B >
            |   < Z >
     < Y >  ->  < A > < Y > < B >
            |   < B > < Y > < A >
            |   < Z >
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > c
            |   < Z > d
            |   ε }

Resposta

1. Simplificação da gramática livre do contexto

1.1. Exclusão de Produções Vazias

1.1.1. Identificação das variáveis que constituem produções vazias

Conjunto de variáveis que constituem produções vazias
Iteração Variáveis
0
1 {Z}
2 {Z, X, Y}
3 {Z, X, Y, S}
4 {Z, X, Y, S}

1.1.2. Exclusão das produções vazias da gramática

G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < X >
            |   < Y >
            |   < Z >
     < X >  ->  < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < Z >
     < Y >  ->  < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z >
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > c
            |   c
            |   < Z > d
            |   d }

1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática

G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < X >
            |   < Y >
            |   < Z >
            |   ε
     < X >  ->  < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < Z >
     < Y >  ->  < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z >
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > c
            |   c
            |   < Z > d
            |   d }

1.2. Exclusão de Produções da Forma < A > -> < B >

1.2.1. Construção dos fechos das variáveis

Fecho(S) = {X, Y, Z}

Fecho(X) = {Z}

Fecho(Y) = {Z}

Fecho(A) = ∅

Fecho(B) = ∅

Fecho(Z) = ∅

1.2.2. Exclusão das produções da forma < A > -> < B >

G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
            |   ε
     < X >  ->  < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
     < Y >  ->  < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > c
            |   c
            |   < Z > d
            |   d }

1.3. Exclusão de Símbolos Inúteis

1.3.1. Identificação das variáveis que constituem terminais

Conjunto de variáveis que constituem terminais
Iteração Variáveis
0
1 {S, X, Y, A, B, Z}
2 {S, X, Y, A, B, Z}
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
            |   ε
     < X >  ->  < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
     < Y >  ->  < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > c
            |   c
            |   < Z > d
            |   d }

1.3.2. 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, X, Y, A, B, Z} {c, d}
2 {S, X, Y, A, B, Z} {c, d, a, b}
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
            |   ε
     < X >  ->  < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
     < Y >  ->  < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > c
            |   c
            |   < Z > d
            |   d
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > c
            |   c
            |   < Z > d
            |   d }

2. Conversão das produções contendo terminais para a forma < A > -> a

G = ({S, X, Y, A, B, Z, C₀, C₁, C₂, C₃, D₀, D₁, D₂, D₃}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < Y > < Z >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > < C₀ >
            |   c
            |   < Z > < D₀ >
            |   d
            |   ε
     < X >  ->  < A > < X > < A >
            |   < A > < A >
            |   < B > < X > < B >
            |   < B > < B >
            |   < Z > < C₁ >
            |   c
            |   < Z > < D₁ >
            |   d
     < Y >  ->  < A > < Y > < B >
            |   < A > < B >
            |   < B > < Y > < A >
            |   < B > < A >
            |   < Z > < C₂ >
            |   c
            |   < Z > < D₂ >
            |   d
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > < C₃ >
            |   c
            |   < Z > < D₃ >
            |   d
     < C₀ > ->  c
     < C₁ > ->  c
     < C₂ > ->  c
     < C₃ > ->  c
     < D₀ > ->  d
     < D₁ > ->  d
     < D₂ > ->  d
     < D₃ > ->  d  }

3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >

G = ({S, S₀, S₁, S₂, S₃, S₄, X, X₀, X₁, Y, Y₀, Y₁, A, B, Z, C₀, C₁, C₂, C₃, D₀, D₁, D₂, D₃}, {a, b, c, d}, P, S)
P = {< S >  ->  < X > < S₀ >
            |   < X > < Y >
            |   < X > < Z >
            |   < Y > < Z >
            |   < A > < S₁ >
            |   < A > < A >
            |   < B > < S₂ >
            |   < B > < B >
            |   < A > < S₃ >
            |   < A > < B >
            |   < B > < S₄ >
            |   < B > < A >
            |   < Z > < C₀ >
            |   c
            |   < Z > < D₀ >
            |   d
            |   ε
     < S₀ > ->  < Y > < Z >
     < S₁ > ->  < X > < A >
     < S₂ > ->  < X > < B >
     < S₃ > ->  < Y > < B >
     < S₄ > ->  < Y > < A >
     < X >  ->  < A > < X₀ >
            |   < A > < A >
            |   < B > < X₁ >
            |   < B > < B >
            |   < Z > < C₁ >
            |   c
            |   < Z > < D₁ >
            |   d
     < X₀ > ->  < X > < A >
     < X₁ > ->  < X > < B >
     < Y >  ->  < A > < Y₀ >
            |   < A > < B >
            |   < B > < Y₁ >
            |   < B > < A >
            |   < Z > < C₂ >
            |   c
            |   < Z > < D₂ >
            |   d
     < Y₀ > ->  < Y > < B >
     < Y₁ > ->  < Y > < A >
     < A >  ->  a
     < B >  ->  b
     < Z >  ->  < Z > < C₃ >
            |   c
            |   < Z > < D₃ >
            |   d
     < C₀ > ->  c
     < C₁ > ->  c
     < C₂ > ->  c
     < C₃ > ->  c
     < D₀ > ->  d
     < D₁ > ->  d
     < D₂ > ->  d
     < D₃ > ->  d  }

Recomendamos

Kinghost Copy Revista Segurança Digital