Exercício 08.44

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

G = ({S, A, B, C, D, E, F}, {w, x, y, z}, P, S)
P = {< S >  ->  < A > x < C > y
            |   < C >
            |   z < B > < A > w
     < A >  ->  < E > < S > w
            |   z < A > y < C >
            |   x
     < B >  ->  < C > w < E >
            |   < E > x y
            |   < B > < F > < A >
     < C >  ->  y < A > x y
            |   ε
            |   < B > < D > w
     < D >  ->  < S > y z < A >
            |   x
            |   w < E > y
     < E >  ->  < F > x z < B >
            |   < D > < S > < E >
     < F >  ->  < D > y
            |   < C > < S >
            |   < S > < 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 {C}
2 {C, S}
3 {C, S, F}
4 {C, S, F}

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

G = ({S, A, B, C, D, E, F}, {w, x, y, z}, P, S)
P = {< S >  ->  < A > x < C > y
            |   < A > x y
            |   < C >
            |   z < B > < A > w
     < A >  ->  < E > < S > w
            |   < E > w
            |   z < A > y < C >
            |   z < A > y
            |   x
     < B >  ->  < C > w < E >
            |   w < E >
            |   < E > x y
            |   < B > < F > < A >
            |   < B > < A >
     < C >  ->  y < A > x y
            |   < B > < D > w
     < D >  ->  < S > y z < A >
            |   y z < A >
            |   x
            |   w < E > y
     < E >  ->  < F > x z < B >
            |   x z < B >
            |   < D > < S > < E >
            |   < D > < E >
     < F >  ->  < D > y
            |   < C > < S >
            |   < C >
            |   < S >
            |   < S > < B > z
            |   < B > z }

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

G = ({S, A, B, C, D, E, F}, {w, x, y, z}, P, S)
P = {< S >  ->  < A > x < C > y
            |   < A > x y
            |   < C >
            |   z < B > < A > w
            |   ε
     < A >  ->  < E > < S > w
            |   < E > w
            |   z < A > y < C >
            |   z < A > y
            |   x
     < B >  ->  < C > w < E >
            |   w < E >
            |   < E > x y
            |   < B > < F > < A >
            |   < B > < A >
     < C >  ->  y < A > x y
            |   < B > < D > w
     < D >  ->  < S > y z < A >
            |   y z < A >
            |   x
            |   w < E > y
     < E >  ->  < F > x z < B >
            |   x z < B >
            |   < D > < S > < E >
            |   < D > < E >
     < F >  ->  < D > y
            |   < C > < S >
            |   < C >
            |   < S >
            |   < S > < B > z
            |   < B > z }

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

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

Fecho(S) = {C}

Fecho(A) = ∅

Fecho(B) = ∅

Fecho(C) = ∅

Fecho(D) = ∅

Fecho(E) = ∅

Fecho(F) = {S, C}

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

G = ({S, A, B, C, D, E, F}, {w, x, y, z}, P, S)
P = {< S >  ->  < A > x < C > y
            |   < A > x y
            |   y < A > x y
            |   < B > < D > w
            |   z < B > < A > w
            |   ε
     < A >  ->  < E > < S > w
            |   < E > w
            |   z < A > y < C >
            |   z < A > y
            |   x
     < B >  ->  < C > w < E >
            |   w < E >
            |   < E > x y
            |   < B > < F > < A >
            |   < B > < A >
     < C >  ->  y < A > x y
            |   < B > < D > w
     < D >  ->  < S > y z < A >
            |   y z < A >
            |   x
            |   w < E > y
     < E >  ->  < F > x z < B >
            |   x z < B >
            |   < D > < S > < E >
            |   < D > < E >
     < F >  ->  < D > y
            |   < C > < S >
            |   < A > x < C > y
            |   < A > x y
            |   y < A > x y
            |   < B > < D > w
            |   z < B > < A > w
            |   < S > < B > z
            |   < B > z }

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 {A, D}
2 {A, D, S, C, F}
3 {A, D, S, C, F}
G = ({S, A, C, D, F}, {w, x, y, z}, P, S)
P = {< S >  ->  < A > x < C > y
            |   < A > x y
            |   y < A > x y
            |   ε
     < A >  ->  z < A > y < C >
            |   z < A > y
            |   x
     < C >  ->  y < A > x y
     < D >  ->  < S > y z < A >
            |   y z < A >
            |   x
     < F >  ->  < D > y
            |   < C > < S >
            |   < A > x < C > y
            |   < A > x y
            |   y < A > x y }

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, A, C} {x, y}
2 {S, A, C} {x, y, z}
G = ({S, A, C}, {x, y, z}, P, S)
P = {< S >  ->  < A > x < C > y
            |   < A > x y
            |   y < A > x y
            |   ε
     < A >  ->  z < A > y < C >
            |   z < A > y
            |   x
     < C >  ->  y < A > x y }

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

G = ({S, A, C, X₀, X₁, X₂, X₃, Y₀, Y₁, Y₂, Y₃, Y₄, Y₅, Y₆, Y₇, Z₀, Z₁}, {x, y, z}, P, S)
P = {< S >  ->  < A > < X₀ > < C > < Y₀ >
            |   < A > < X₁ > < Y₁ >
            |   < Y₂ > < A > < X₂ > < Y₃ >
            |   ε
     < A >  ->  < Z₀ > < A > < Y₄ > < C >
            |   < Z₁ > < A > < Y₅ >
            |   x
     < C >  ->  < Y₆ > < A > < X₃ > < Y₇ >
     < X₀ > ->  x
     < X₁ > ->  x
     < X₂ > ->  x
     < X₃ > ->  x
     < Y₀ > ->  y
     < Y₁ > ->  y
     < Y₂ > ->  y
     < Y₃ > ->  y
     < Y₄ > ->  y
     < Y₅ > ->  y
     < Y₆ > ->  y
     < Y₇ > ->  y
     < Z₀ > ->  z
     < Z₁ > ->  z }

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

G = ({S, S₀, S₁, S₂, S₃, S₄, A, A₀, A₁, A₂, C, C₀, C₁, X₀, X₁, X₂, X₃, Y₀, Y₁, Y₂, Y₃, Y₄, Y₅, Y₆, Y₇, Z₀, Z₁}, {x, y, z}, P, S)
P = {< S >  ->  < A > < S₁ >
            |   < A > < S₂ >
            |   < Y₂ > < S₄ >
            |   ε
     < S₀ > ->  < C > < Y₀ >
     < S₁ > ->  < X₀ > < S₀ >
     < S₂ > ->  < X₁ > < Y₁ >
     < S₃ > ->  < X₂ > < Y₃ >
     < S₄ > ->  < A > < S₃ >
     < A >  ->  < Z₀ > < A₁ >
            |   < Z₁ > < A₂ >
            |   x
     < A₀ > ->  < Y₄ > < C >
     < A₁ > ->  < A > < A₀ >
     < A₂ > ->  < A > < Y₅ >
     < C >  ->  < Y₆ > < C₁ >
     < C₀ > ->  < X₃ > < Y₇ >
     < C₁ > ->  < A > < C₀ >
     < X₀ > ->  x
     < X₁ > ->  x
     < X₂ > ->  x
     < X₃ > ->  x
     < Y₀ > ->  y
     < Y₁ > ->  y
     < Y₂ > ->  y
     < Y₃ > ->  y
     < Y₄ > ->  y
     < Y₅ > ->  y
     < Y₆ > ->  y
     < Y₇ > ->  y
     < Z₀ > ->  z
     < Z₁ > ->  z }

Recomendamos

Kinghost Java Magazine Duolingo