Exercício 08.18

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

G = ({S, A, B}, {a, b}, P, S)
P = {< S > ::= a b < A > < B >
     < A > ::= b < A > < B >
            |  ε
     < B > ::= < B > < A > a
            |  < A > }

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 {A}
2 {A, B}
2 {A, B}

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

G = ({S, A, B}, {a, b}, P, S)
P = {< S > ::= a b < A > < B >
            |  a b < A >
            |  a b < B >
            |  a b
     < A > ::= b < A > < B >
            |  b < A >
            |  b < B >
            |  b
     < B > ::= < B > < A > a
            |  < A > a
            |  < B > a
            |  a
            |  < A > }

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

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

Fecho(S) = ∅

Fecho(A) = ∅

Fecho(B) = {A}

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

G = ({S, A, B}, {a, b}, P, S)
P = {< S > ::= a b < A > < B >
            |  a b < A >
            |  a b < B >
            |  a b
     < A > ::= b < A > < B >
            |  b < A >
            |  b < B >
            |  b
     < B > ::= < B > < A > a
            |  < A > a
            |  < B > a
            |  a
            |  b < A > < B >
            |  b < A >
            |  b < B >
            |  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 {S, A, B}
2 {S, A, B}
G = ({S, A, B}, {a, b}, P, S)
P = {< S > ::= a b < A > < B >
            |  a b < A >
            |  a b < B >
            |  a b
     < A > ::= b < A > < B >
            |  b < A >
            |  b < B >
            |  b
     < B > ::= < B > < A > a
            |  < A > a
            |  < B > a
            |  a
            |  b < A > < B >
            |  b < A >
            |  b < B >
            |  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 {S}
1 {S, A, B} {a, b}
2 {S, A, B} {a, b}
G = ({S, A, B}, {a, b}, P, S)
P = {< S > ::= a b < A > < B >
            |  a b < A >
            |  a b < B >
            |  a b
     < A > ::= b < A > < B >
            |  b < A >
            |  b < B >
            |  b
     < B > ::= < B > < A > a
            |  < A > a
            |  < B > a
            |  a
            |  b < A > < B >
            |  b < A >
            |  b < B >
            |  b }

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

G = ({S, A, B, X₀, X₁, X₂, X₃, X₄, X₅, X₆, Y₀, Y₁, Y₂, Y₃, Y₄, Y₅, Y₆, Y₇, Y₈, Y₉}, {a, b}, P, S)
P = {< S >  ::= < X₀ > < Y₀ > < A > < B >
             |  < X₁ > < Y₁ > < A >
             |  < X₂ > < Y₂ > < B >
             |  < X₃ > < Y₃ >
     < A >  ::= < Y₄ > < A > < B >
             |  < Y₅ > < A >
             |  < Y₆ > < B >
             |  b
     < B >  ::= < B > < A > < X₄ >
             |  < A > < X₅ >
             |  < B > < X₆ >
             |  a
             |  < Y₇ > < A > < B >
             |  < Y₈ > < A >
             |  < Y₉ > < B >
             |  b
     < X₀ > ::= a
     < X₁ > ::= a
     < X₂ > ::= a
     < X₃ > ::= a
     < X₄ > ::= a
     < X₅ > ::= a
     < X₆ > ::= a
     < Y₀ > ::= b
     < Y₁ > ::= b
     < Y₂ > ::= b
     < Y₃ > ::= b
     < Y₄ > ::= b
     < Y₅ > ::= b
     < Y₆ > ::= b
     < Y₇ > ::= b
     < Y₈ > ::= b
     < Y₉ > ::= b }

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

G = ({S, S₀, S₁, S₂, S₃, A, A₀, B, B₀, B₁, X₀, X₁, X₂, X₃, X₄, X₅, X₆, Y₀, Y₁, Y₂, Y₃, Y₄, Y₅, Y₆, Y₇, Y₈, Y₉}, {a, b}, P, S)
P = {< S >  ::= < X₀ > < S₁ >
             |  < X₁ > < S₂ >
             |  < X₂ > < S₃ >
             |  < X₃ > < Y₃ >
     < S₀ > ::= < A > < B >
     < S₁ > ::= < Y₀ > < S₀ >
     < S₂ > ::= < Y₁ > < A >
     < S₃ > ::= < Y₂ > < B >
     < A >  ::= < Y₄ > < A₀ >
             |  < Y₅ > < A >
             |  < Y₆ > < B >
             |  b
     < A₀ > ::= < A > < B >
     < B >  ::= < B > < B₀ >
             |  < A > < X₅ >
             |  < B > < X₆ >
             |  a
             |  < Y₇ > < B₁ >
             |  < Y₈ > < A >
             |  < Y₉ > < B >
             |  b
     < B₀ > ::= < A > < X₄ >
     < B₁ > ::= < A > < B >
     < X₀ > ::= a
     < X₁ > ::= a
     < X₂ > ::= a
     < X₃ > ::= a
     < X₄ > ::= a
     < X₅ > ::= a
     < X₆ > ::= a
     < Y₀ > ::= b
     < Y₁ > ::= b
     < Y₂ > ::= b
     < Y₃ > ::= b
     < Y₄ > ::= b
     < Y₅ > ::= b
     < Y₆ > ::= b
     < Y₇ > ::= b
     < Y₈ > ::= b
     < Y₉ > ::= b }

Recomendamos

Copy Clique Alimentos Um Sábado Qualquer