Exercício 08.26

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

G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X >  ->  < K > < W >
            |   a < K >
     < Y >  ->  ε
            |   < X > < W > b
     < Z >  ->  < X > < K >
            |   < Y >
            |   c < K >
     < K >  ->  b
            |   < X > < W > a
     < W >  ->  < Y >
            |   < X > b < Y >
     < T >  ->  c < Z > < Y >
            |   < Y > b < Z > }

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 {Y}
2 {Y, Z, W}
3 {Y, Z, W}

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

G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X >  ->  < K > < W >
            |   < K >
            |   a < K >
     < Y >  ->  < X > < W > b
            |   < X > b
     < Z >  ->  < X > < K >
            |   < Y >
            |   c < K >
     < K >  ->  b
            |   < X > < W > a
            |   < X > a
     < W >  ->  < Y >
            |   < X > b < Y >
            |   < X > b
     < T >  ->  c < Z > < Y >
            |   c < Z >
            |   c < Y >
            |   c
            |   < Y > b < Z >
            |   < Y > b
            |   b < Z >
            |   b  }

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

G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X >  ->  < K > < W >
            |   < K >
            |   a < K >
     < Y >  ->  < X > < W > b
            |   < X > b
     < Z >  ->  < X > < K >
            |   < Y >
            |   c < K >
     < K >  ->  b
            |   < X > < W > a
            |   < X > a
     < W >  ->  < Y >
            |   < X > b < Y >
            |   < X > b
     < T >  ->  c < Z > < Y >
            |   c < Z >
            |   c < Y >
            |   c
            |   < Y > b < Z >
            |   < Y > b
            |   b < Z >
            |   b  }

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

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

Fecho(X) = {K}

Fecho(Y) = ∅

Fecho(Z) = {Y}

Fecho(K) = ∅

Fecho(W) = {Y}

Fecho(T) = ∅

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

G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X >  ->  < K > < W >
            |   b
            |   < X > < W > a
            |   < X > a
            |   a < K >
     < Y >  ->  < X > < W > b
            |   < X > b
     < Z >  ->  < X > < K >
            |   < X > < W > b
            |   < X > b
            |   c < K >
     < K >  ->  b
            |   < X > < W > a
            |   < X > a
     < W >  ->  < X > < W > b
            |   < X > b
            |   < X > b < Y >
     < T >  ->  c < Z > < Y >
            |   c < Z >
            |   c < Y >
            |   c
            |   < Y > b < Z >
            |   < Y > b
            |   b < Z >
            |   b  }

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 {X, K, T}
2 {X, K, T, Y, Z, W}
3 {X, K, T, Y, Z, W}
G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X >  ->  < K > < W >
            |   b
            |   < X > < W > a
            |   < X > a
            |   a < K >
     < Y >  ->  < X > < W > b
            |   < X > b
     < Z >  ->  < X > < K >
            |   < X > < W > b
            |   < X > b
            |   c < K >
     < K >  ->  b
            |   < X > < W > a
            |   < X > a
     < W >  ->  < X > < W > b
            |   < X > b
            |   < X > b < Y >
     < T >  ->  c < Z > < Y >
            |   c < Z >
            |   c < Y >
            |   c
            |   < Y > b < Z >
            |   < Y > b
            |   b < Z >
            |   b  }

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 {X}
1 {X, K, W} {a, b}
2 {X, K, W, Y} {a, b}
3 {X, K, W, Y} {a, b}
G = ({X, Y, K, W}, {a, b}, P, X)
P = {< X >  ->  < K > < W >
            |   b
            |   < X > < W > a
            |   < X > a
            |   a < K >
     < Y >  ->  < X > < W > b
            |   < X > b
     < K >  ->  b
            |   < X > < W > a
            |   < X > a
     < W >  ->  < X > < W > b
            |   < X > b
            |   < X > b < Y > }

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

G = ({X, Y, K, W, A₀, A₁, A₂, A₃, A₄, B₀, B₁, B₂, B₃, B₄}, {a, b}, P, X)
P = {< X >  ->  < K > < W >
            |   b
            |   < X > < W > < A₀ >
            |   < X > < A₁ >
            |   < A₂ > < K >
     < Y >  ->  < X > < W > < B₀ >
            |   < X > < B₁ >
     < K >  ->  b
            |   < X > < W > < A₃ >
            |   < X > < A₄ >
     < W >  ->  < X > < W > < B₂ >
            |   < X > < B₃ >
            |   < X > < B₄ > < Y >
     < A₀ > ->  a
     < A₁ > ->  a
     < A₂ > ->  a
     < A₃ > ->  a
     < A₄ > ->  a
     < B₀ > ->  b
     < B₁ > ->  b
     < B₂ > ->  b
     < B₃ > ->  b
     < B₄ > ->  b  }

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

G = ({X, Y, K, W, A₀, A₁, A₂, A₃, A₄, B₀, B₁, B₂, B₃, B₄, X₀, Y₀, K₀, W₀, W₁}, {a, b}, P, X)
P = {< X >  ->  < K > < W >
            |   b
            |   < X > < X₀ >
            |   < X > < A₁ >
            |   < A₂ > < K >
     < X₀ > ->  < W > < A₀ >
     < Y >  ->  < X > < Y₀ >
            |   < X > < B₁ >
     < Y₀ > ->  < W > < B₀ >
     < K >  ->  b
            |   < X > < K₀ >
            |   < X > < A₄ >
     < K₀ > ->  < W > < A₃ >
     < W >  ->  < X > < W₀ >
            |   < X > < B₃ >
            |   < X > < W₁ >
     < W₀ > ->  < W > < B₂ >
     < W₁ > ->  < B₄ > < Y >
     < A₀ > ->  a
     < A₁ > ->  a
     < A₂ > ->  a
     < A₃ > ->  a
     < A₄ > ->  a
     < B₀ > ->  b
     < B₁ > ->  b
     < B₂ > ->  b
     < B₃ > ->  b
     < B₄ > ->  b  }

Recomendamos

Revista Digital Copy Duolingo