Exercício 08.17
Converta para a Forma Normal de Chomsky a gramática:
G = ({S, A, B}, {a, b}, P, S)
P = {< S > -> a < A > < B >
< A > -> b < B > b
< B > -> < A >
| ε }
Converta para a Forma Normal de Chomsky a gramática:
G = ({S, A, B}, {a, b}, P, S)
P = {< S > -> a < A > < B >
< A > -> b < B > b
< B > -> < A >
| ε }
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 | {B} |
2 | {B} |
1.1.2. Exclusão das produções vazias da gramática
G = ({S, A, B}, {a, b}, P, S)
P = {< S > -> a < A > < B >
| a < A >
< A > -> b < B > b
| b b
< B > -> < A > }
1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática
G = ({S, A, B}, {a, b}, P, S)
P = {< S > -> a < A > < B >
| a < A >
< A > -> b < B > b
| b b
< B > -> < 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 < A > < B >
| a < A >
< A > -> b < B > b
| b b
< B > -> b < B > 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 | {A, B} |
2 | {A, B, S} |
3 | {A, B, S} |
G = ({S, A, B}, {a, b}, P, S)
P = {< S > -> a < A > < B >
| a < A >
< A > -> b < B > b
| b b
< B > -> b < B > 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} |
2 | {S, A, B} | {a, b} |
G = ({S, A, B}, {a, b}, P, S)
P = {< S > -> a < A > < B >
| a < A >
< A > -> b < B > b
| b b
< B > -> b < B > b
| b b }
2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({S, A, A₀, A₁, B, B₀, B₁, B₂, B₃, B₄, B₅, B₆, B₇}, {a, b}, P, S)
P = {< S > -> < A₀ > < A > < B >
| < A₁ > < A >
< A > -> < B₀ > < B > < B₁ >
| < B₂ > < B₃ >
< B > -> < B₄ > < B > < B₅ >
| < B₆ > < B₇ >
< A₀ > -> a
< A₁ > -> a
< B₀ > -> b
< B₁ > -> b
< B₂ > -> b
< 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 = ({S, S₀, A, A₀, A₁, A₂, B, B₀, B₁, B₂, B₃, B₄, B₅, B₆, B₇, B₈}, {a, b}, P, S)
P = {< S > -> < A₀ > < S₀ >
| < A₁ > < A >
< S₀ > -> < A > < B >
< A > -> < B₀ > < A₂ >
| < B₂ > < B₃ >
< A₂ > -> < B > < B₁ >
< B > -> < B₄ > < B₈ >
| < B₆ > < B₇ >
< B₈ > -> < B > < B₅ >
< A₀ > -> a
< A₁ > -> a
< B₀ > -> b
< B₁ > -> b
< B₂ > -> b
< B₃ > -> b
< B₄ > -> b
< B₅ > -> b
< B₆ > -> b
< B₇ > -> b }