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
| 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
| 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
| 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
