Exercício 08.42

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

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

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

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 >  ->  < E > x y
            |   z < D >
            |   z
     < B >  ->  < D > < F >
            |   < D >
            |   < F >
            |   x < C > y
     < C >  ->  x < E > < B >
            |   x < E >
            |   < F > < C > z
            |   < C > z
     < D >  ->  y < C > < A >
            |   < A > < F > < A >
            |   < A > < A >
     < E >  ->  < A > z < C >
            |   < B > < E > y z
            |   < E > y z
     < F >  ->  z < A > y
            |   < D >
            |   < A > < C > < B >
            |   < A > < C > }

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 >  ->  < E > x y
            |   z < D >
            |   z
     < B >  ->  < D > < F >
            |   < D >
            |   < F >
            |   x < C > y
     < C >  ->  x < E > < B >
            |   x < E >
            |   < F > < C > z
            |   < C > z
     < D >  ->  y < C > < A >
            |   < A > < F > < A >
            |   < A > < A >
     < E >  ->  < A > z < C >
            |   < B > < E > y z
            |   < E > y z
     < F >  ->  z < A > y
            |   < D >
            |   < A > < C > < B >
            |   < A > < C > }

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) = {D, F}

Fecho(C) = ∅

Fecho(D) = ∅

Fecho(E) = ∅

Fecho(F) = {D}

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 >  ->  < E > x y
            |   z < D >
            |   z
     < B >  ->  < D > < F >
            |   z < A > y
            |   y < C > < A >
            |   < A > < F > < A >
            |   < A > < A >
            |   < A > < C > < B >
            |   < A > < C >
            |   x < C > y
     < C >  ->  x < E > < B >
            |   x < E >
            |   < F > < C > z
            |   < C > z
     < D >  ->  y < C > < A >
            |   < A > < F > < A >
            |   < A > < A >
     < E >  ->  < A > z < C >
            |   < B > < E > y z
            |   < E > y z
     < F >  ->  z < A > y
            |   y < C > < A >
            |   < A > < F > < A >
            |   < A > < A >
            |   < A > < C > < B >
            |   < A > < C > }

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

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

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

G = ({A, D, F, Y₀, Z₀, Z₁}, {y, z}, P, A)
P = {< A >  ->  < Z₀ > < D >
            |   z
     < D >  ->  < A > < F > < A >
            |   < A > < A >
     < F >  ->  < Z₁ > < A > < Y₀ >
            |   < A > < F > < A >
            |   < A > < A >
     < Y₀ > ->  y
     < Z₀ > ->  z
     < Z₁ > ->  z }

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

G = ({A, D, D₀, F, F₀, F₁, Y₀, Z₀, Z₁}, {y, z}, P, A)
P = {< A >  ->  < Z₀ > < D >
            |   z
     < D >  ->  < A > < D₀ >
            |   < A > < A >
     < F >  ->  < Z₁ > < F₀ >
            |   < A > < F₁ >
            |   < A > < A >
     < D₀ > ->  < F > < A >
     < F₀ > ->  < A > < Y₀ >
     < F₁ > ->  < F > < A >
     < Y₀ > ->  y
     < Z₀ > ->  z
     < Z₁ > ->  z }

Recomendamos

Copy Clique Alimentos Clickarvore