Exercício 08.19

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

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

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	{S}
2	{S}

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

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

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 > < S > < B >
            |   < A > < B >
            |   ε
     < A >  ->  a < A > < S >
            |   a < A >
            |   a
     < B >  ->  < S > b < S >
            |   < S > b
            |   b < S >
            |   b
            |   < A >
            |   b b }

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 > < S > < B >
            |   < A > < B >
            |   ε
     < A >  ->  a < A > < S >
            |   a < A >
            |   a
     < B >  ->  < S > b < S >
            |   < S > b
            |   b < S >
            |   b
            |   a < A > < S >
            |   a < A >
            |   a
            |   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	{A, B}
2	{A, B, S}
3	{A, B, S}

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

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

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

G = ({S, A, B, X₀, X₁, X₂, X₃, Y₀, Y₁, Y₂, Y₃, Y₄}, {a, b}, P, S)
P = {< S >  ->  < A > < S > < B >
            |   < A > < B >
            |   ε
     < A >  ->  < X₀ > < A > < S >
            |   < X₁ > < A >
            |   a
     < B >  ->  < S > < Y₀ > < S >
            |   < S > < Y₁ >
            |   < Y₂ > < S >
            |   b
            |   < X₂ > < A > < S >
            |   < X₃ > < A >
            |   a
            |   < Y₃ > < Y₄ >
     < X₀ > ->  a
     < X₁ > ->  a
     < X₂ > ->  a
     < X₃ > ->  a
     < 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₀, A, A₀, B, B₀, B₁, X₀, X₁, X₂, X₃, Y₀, Y₁, Y₂, Y₃, Y₄}, {a, b}, P, S)
P = {< S >  ->  < A > < S₀ >
            |   < A > < B >
            |   ε
     < S₀ > ->  < S > < B >
     < A >  ->  < X₀ > < A₀ >
            |   < X₁ > < A >
            |   a
     < A₀ > ->  < A > < S >
     < B >  ->  < S > < B₀ >
            |   < S > < Y₁ >
            |   < Y₂ > < S >
            |   b
            |   < X₂ < B₁ >
            |   < X₃ > < A >
            |   a
            |   < Y₃ > < Y₄ >
     < B₀ > ->  < Y₀ > < S >
     < B₁ > ->  > < A > < S >
     < X₀ > ->  a
     < X₁ > ->  a
     < X₂ > ->  a
     < X₃ > ->  a
     < Y₀ > ->  b
     < Y₁ > ->  b
     < Y₂ > ->  b
     < Y₃ > ->  b
     < Y₄ > ->  b }