Converta para a Forma Normal de Chomsky a gramática:
G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X > -> < K > < W >
| a < K >
< Y > -> ε
| < X > < W > b
< Z > -> < X > < K >
| < Y >
| c < K >
< K > -> b
| < X > < W > a
< W > -> < Y >
| < X > b < Y >
< T > -> c < Z > < Y >
| < Y > b < Z > }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 | {Y} |
| 2 | {Y, Z, W} |
| 3 | {Y, Z, W} |
1.1.2. Exclusão das produções vazias da gramática
G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X > -> < K > < W >
| < K >
| a < K >
< Y > -> < X > < W > b
| < X > b
< Z > -> < X > < K >
| < Y >
| c < K >
< K > -> b
| < X > < W > a
| < X > a
< W > -> < Y >
| < X > b < Y >
| < X > b
< T > -> c < Z > < Y >
| c < Z >
| c < Y >
| c
| < Y > b < Z >
| < Y > b
| b < Z >
| b }1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática
G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X > -> < K > < W >
| < K >
| a < K >
< Y > -> < X > < W > b
| < X > b
< Z > -> < X > < K >
| < Y >
| c < K >
< K > -> b
| < X > < W > a
| < X > a
< W > -> < Y >
| < X > b < Y >
| < X > b
< T > -> c < Z > < Y >
| c < Z >
| c < Y >
| c
| < Y > b < Z >
| < Y > b
| b < Z >
| b }1.2. Exclusão de Produções da Forma < A > -> < B >
1.2.1. Construção dos fechos das variáveis
Fecho(X) = {K}
Fecho(Y) = ∅
Fecho(Z) = {Y}
Fecho(K) = ∅
Fecho(W) = {Y}
Fecho(T) = ∅
1.2.2. Exclusão das produções da forma < A > -> < B >
G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X > -> < K > < W >
| b
| < X > < W > a
| < X > a
| a < K >
< Y > -> < X > < W > b
| < X > b
< Z > -> < X > < K >
| < X > < W > b
| < X > b
| c < K >
< K > -> b
| < X > < W > a
| < X > a
< W > -> < X > < W > b
| < X > b
| < X > b < Y >
< T > -> c < Z > < Y >
| c < Z >
| c < Y >
| c
| < Y > b < Z >
| < Y > b
| b < Z >
| 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 | {X, K, T} |
| 2 | {X, K, T, Y, Z, W} |
| 3 | {X, K, T, Y, Z, W} |
G = ({X, Y, Z, K, W, T}, {a, b, c}, P, X)
P = {< X > -> < K > < W >
| b
| < X > < W > a
| < X > a
| a < K >
< Y > -> < X > < W > b
| < X > b
< Z > -> < X > < K >
| < X > < W > b
| < X > b
| c < K >
< K > -> b
| < X > < W > a
| < X > a
< W > -> < X > < W > b
| < X > b
| < X > b < Y >
< T > -> c < Z > < Y >
| c < Z >
| c < Y >
| c
| < Y > b < Z >
| < Y > b
| b < Z >
| b }1.3.2. Identificação dos símbolos alcançáveis a partir do símbolo inicial
| Iteração | Variáveis | Terminais |
|---|---|---|
| 0 | {X} | ∅ |
| 1 | {X, K, W} | {a, b} |
| 2 | {X, K, W, Y} | {a, b} |
| 3 | {X, K, W, Y} | {a, b} |
G = ({X, Y, K, W}, {a, b}, P, X)
P = {< X > -> < K > < W >
| b
| < X > < W > a
| < X > a
| a < K >
< Y > -> < X > < W > b
| < X > b
< K > -> b
| < X > < W > a
| < X > a
< W > -> < X > < W > b
| < X > b
| < X > b < Y > }2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({X, Y, K, W, A₀, A₁, A₂, A₃, A₄, B₀, B₁, B₂, B₃, B₄}, {a, b}, P, X)
P = {< X > -> < K > < W >
| b
| < X > < W > < A₀ >
| < X > < A₁ >
| < A₂ > < K >
< Y > -> < X > < W > < B₀ >
| < X > < B₁ >
< K > -> b
| < X > < W > < A₃ >
| < X > < A₄ >
< W > -> < X > < W > < B₂ >
| < X > < B₃ >
| < X > < B₄ > < Y >
< A₀ > -> a
< A₁ > -> a
< A₂ > -> a
< A₃ > -> a
< A₄ > -> a
< B₀ > -> b
< B₁ > -> b
< B₂ > -> b
< B₃ > -> b
< B₄ > -> b }3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >
G = ({X, Y, K, W, A₀, A₁, A₂, A₃, A₄, B₀, B₁, B₂, B₃, B₄, X₀, Y₀, K₀, W₀, W₁}, {a, b}, P, X)
P = {< X > -> < K > < W >
| b
| < X > < X₀ >
| < X > < A₁ >
| < A₂ > < K >
< X₀ > -> < W > < A₀ >
< Y > -> < X > < Y₀ >
| < X > < B₁ >
< Y₀ > -> < W > < B₀ >
< K > -> b
| < X > < K₀ >
| < X > < A₄ >
< K₀ > -> < W > < A₃ >
< W > -> < X > < W₀ >
| < X > < B₃ >
| < X > < W₁ >
< W₀ > -> < W > < B₂ >
< W₁ > -> < B₄ > < Y >
< A₀ > -> a
< A₁ > -> a
< A₂ > -> a
< A₃ > -> a
< A₄ > -> a
< B₀ > -> b
< B₁ > -> b
< B₂ > -> b
< B₃ > -> b
< B₄ > -> b }
