Exercício 08.25

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

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

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, D}
3	{C, D}

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

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

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

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

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

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

Fecho(A) = ∅

Fecho(B) = ∅

Fecho(C) = ∅

Fecho(D) = {C}

Fecho(E) = ∅

Fecho(F) = {E}

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

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

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	{B, E, F}
2	{B, E, F, A, C, D}
3	{B, E, F, A, C, D}

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

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	{A}	∅
1	{A, B, F}	{x, y, z}
2	{A, B, F, C, D}	{x, y, z}
3	{A, B, F, C, D}	{x, y, z}

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

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

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

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

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