Converta para a Forma Normal de Chomsky a gramática:
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
< X > -> < A > < X > < A >
| < B > < X > < B >
| < Z >
< Y > -> < A > < Y > < B >
| < B > < Y > < A >
| < Z >
< A > -> a
< B > -> b
< Z > -> < Z > c
| < Z > d
| ε }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 | {Z} |
| 2 | {Z, X, Y} |
| 3 | {Z, X, Y, S} |
| 4 | {Z, X, Y, S} |
1.1.2. Exclusão das produções vazias da gramática
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < X >
| < Y >
| < Z >
< X > -> < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < Z >
< Y > -> < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z >
< A > -> a
< B > -> b
< Z > -> < Z > c
| c
| < Z > d
| d }1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < X >
| < Y >
| < Z >
| ε
< X > -> < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < Z >
< Y > -> < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z >
< A > -> a
< B > -> b
< Z > -> < Z > c
| c
| < Z > d
| d }1.2. Exclusão de Produções da Forma < A > -> < B >
1.2.1. Construção dos fechos das variáveis
Fecho(S) = {X, Y, Z}
Fecho(X) = {Z}
Fecho(Y) = {Z}
Fecho(A) = ∅
Fecho(B) = ∅
Fecho(Z) = ∅
1.2.2. Exclusão das produções da forma < A > -> < B >
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > c
| c
| < Z > d
| d
| ε
< X > -> < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < Z > c
| c
| < Z > d
| d
< Y > -> < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > c
| c
| < Z > d
| d
< A > -> a
< B > -> b
< Z > -> < Z > c
| c
| < Z > d
| d }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, X, Y, A, B, Z} |
| 2 | {S, X, Y, A, B, Z} |
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > c
| c
| < Z > d
| d
| ε
< X > -> < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < Z > c
| c
| < Z > d
| d
< Y > -> < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > c
| c
| < Z > d
| d
< A > -> a
< B > -> b
< Z > -> < Z > c
| c
| < Z > d
| d }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, X, Y, A, B, Z} | {c, d} |
| 2 | {S, X, Y, A, B, Z} | {c, d, a, b} |
G = ({S, X, Y, A, B, Z}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > c
| c
| < Z > d
| d
| ε
< X > -> < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < Z > c
| c
| < Z > d
| d
< Y > -> < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > c
| c
| < Z > d
| d
< A > -> a
< B > -> b
< Z > -> < Z > c
| c
| < Z > d
| d }2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({S, X, Y, A, B, Z, C₀, C₁, C₂, C₃, D₀, D₁, D₂, D₃}, {a, b, c, d}, P, S)
P = {< S > -> < X > < Y > < Z >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > < C₀ >
| c
| < Z > < D₀ >
| d
| ε
< X > -> < A > < X > < A >
| < A > < A >
| < B > < X > < B >
| < B > < B >
| < Z > < C₁ >
| c
| < Z > < D₁ >
| d
< Y > -> < A > < Y > < B >
| < A > < B >
| < B > < Y > < A >
| < B > < A >
| < Z > < C₂ >
| c
| < Z > < D₂ >
| d
< A > -> a
< B > -> b
< Z > -> < Z > < C₃ >
| c
| < Z > < D₃ >
| d
< C₀ > -> c
< C₁ > -> c
< C₂ > -> c
< C₃ > -> c
< D₀ > -> d
< D₁ > -> d
< D₂ > -> d
< D₃ > -> d }3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >
G = ({S, S₀, S₁, S₂, S₃, S₄, X, X₀, X₁, Y, Y₀, Y₁, A, B, Z, C₀, C₁, C₂, C₃, D₀, D₁, D₂, D₃}, {a, b, c, d}, P, S)
P = {< S > -> < X > < S₀ >
| < X > < Y >
| < X > < Z >
| < Y > < Z >
| < A > < S₁ >
| < A > < A >
| < B > < S₂ >
| < B > < B >
| < A > < S₃ >
| < A > < B >
| < B > < S₄ >
| < B > < A >
| < Z > < C₀ >
| c
| < Z > < D₀ >
| d
| ε
< S₀ > -> < Y > < Z >
< S₁ > -> < X > < A >
< S₂ > -> < X > < B >
< S₃ > -> < Y > < B >
< S₄ > -> < Y > < A >
< X > -> < A > < X₀ >
| < A > < A >
| < B > < X₁ >
| < B > < B >
| < Z > < C₁ >
| c
| < Z > < D₁ >
| d
< X₀ > -> < X > < A >
< X₁ > -> < X > < B >
< Y > -> < A > < Y₀ >
| < A > < B >
| < B > < Y₁ >
| < B > < A >
| < Z > < C₂ >
| c
| < Z > < D₂ >
| d
< Y₀ > -> < Y > < B >
< Y₁ > -> < Y > < A >
< A > -> a
< B > -> b
< Z > -> < Z > < C₃ >
| c
| < Z > < D₃ >
| d
< C₀ > -> c
< C₁ > -> c
< C₂ > -> c
< C₃ > -> c
< D₀ > -> d
< D₁ > -> d
< D₂ > -> d
< D₃ > -> d }
