Exercício 08.48

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

G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
     < B >  ->  + < C > < B >
            |   - < C > < B >
            |   ε
     < C >  ->  < E > < D >
     < D >  ->  * < E > < D >
            |   / < E > < D >
            |   % < E > < D >
            |   ε
     < E >  ->  < G > < F >
     < F >  ->  ^ < G > < F >
            |   ε
     < G >  ->  ( < A > )
            |   < H >
     < H >  ->  w
            |   x
            |   y
            |   z }

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 {B, D, F}
2 {B, D, F}

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

G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < C >
     < B >  ->  + < C > < B >
            |   + < C >
            |   - < C > < B >
            |   - < C >
     < C >  ->  < E > < D >
            |   < E >
     < D >  ->  * < E > < D >
            |   * < E >
            |   / < E > < D >
            |   / < E >
            |   % < E > < D >
            |   % < E >
     < E >  ->  < G > < F >
            |   < G >
     < F >  ->  ^ < G > < F >
            |   ^ < G >
     < G >  ->  ( < A > )
            |   < H >
     < H >  ->  w
            |   x
            |   y
            |   z }

1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática

G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < C >
     < B >  ->  + < C > < B >
            |   + < C >
            |   - < C > < B >
            |   - < C >
     < C >  ->  < E > < D >
            |   < E >
     < D >  ->  * < E > < D >
            |   * < E >
            |   / < E > < D >
            |   / < E >
            |   % < E > < D >
            |   % < E >
     < E >  ->  < G > < F >
            |   < G >
     < F >  ->  ^ < G > < F >
            |   ^ < G >
     < G >  ->  ( < A > )
            |   < H >
     < H >  ->  w
            |   x
            |   y
            |   z }

1.2. Exclusão de Produções da Forma < A > -> < B >

1.2.1. Construção dos fechos das variáveis

Fecho(A) = {C, E, G, H}

Fecho(B) = ∅

Fecho(C) = {E, G, H}

Fecho(D) = ∅

Fecho(E) = {G, H}

Fecho(F) = ∅

Fecho(G) = {H}

Fecho(H) = ∅

1.2.2. Exclusão das produções da forma < A > -> < B >

G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < B >  ->  + < C > < B >
            |   + < C >
            |   - < C > < B >
            |   - < C >
     < C >  ->  < E > < D >
            |   < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < D >  ->  * < E > < D >
            |   * < E >
            |   / < E > < D >
            |   / < E >
            |   % < E > < D >
            |   % < E >
     < E >  ->  < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < F >  ->  ^ < G > < F >
            |   ^ < G >
     < G >  ->  ( < A > )
            |   w
            |   x
            |   y
            |   z
     < H >  ->  w
            |   x
            |   y
            |   z }

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, C, E, G, H}
2 {A, C, E, G, H, B, D, F}
3 {A, C, E, G, H, B, D, F}
G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < B >  ->  + < C > < B >
            |   + < C >
            |   - < C > < B >
            |   - < C >
     < C >  ->  < E > < D >
            |   < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < D >  ->  * < E > < D >
            |   * < E >
            |   / < E > < D >
            |   / < E >
            |   % < E > < D >
            |   % < E >
     < E >  ->  < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < F >  ->  ^ < G > < F >
            |   ^ < G >
     < G >  ->  ( < A > )
            |   w
            |   x
            |   y
            |   z
     < H >  ->  w
            |   x
            |   y
            |   z }

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 {A}
1 {A, C, B, E, D, G, F} {(, ), w, x, y, z}
2 {A, C, B, E, D, G, F} {(, ), w, x, y, z, +, -, *, /, %, ^}
G = ({A, B, C, D, E, F, G}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < B >  ->  + < C > < B >
            |   + < C >
            |   - < C > < B >
            |   - < C >
     < C >  ->  < E > < D >
            |   < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < D >  ->  * < E > < D >
            |   * < E >
            |   / < E > < D >
            |   / < E >
            |   % < E > < D >
            |   % < E >
     < E >  ->  < G > < F >
            |   ( < A > )
            |   w
            |   x
            |   y
            |   z
     < F >  ->  ^ < G > < F >
            |   ^ < G >
     < G >  ->  ( < A > )
            |   w
            |   x
            |   y
            |   z }

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

G = ({A, B, C, D, E, F, G, (₀, (₁, (₂, (₃, )₀, )₁, )₂, )₃, +₀, +₁, -₀, -₁, *₀, *₁, /₀, /₁, %₀, %₁, ^₀, ^₁}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < G > < F >
            |   < (₀ > < A > < )₀ >
            |   w
            |   x
            |   y
            |   z
     < B >  ->  < +₀ > < C > < B >
            |   < +₁ > < C >
            |   < -₀ > < C > < B >
            |   < -₁ > < C >
     < C >  ->  < E > < D >
            |   < G > < F >
            |   < (₁ > < A > < )₁ >
            |   w
            |   x
            |   y
            |   z
     < D >  ->  < *₀ > < E > < D >
            |   < *₁ > < E >
            |   < /₀ > < E > < D >
            |   < /₁ > < E >
            |   < %₀ > < E > < D >
            |   < %₁ > < E >
     < E >  ->  < G > < F >
            |   < (₂ > < A > < )₂ >
            |   w
            |   x
            |   y
            |   z
     < F >  ->  < ^₀ > < G > < F >
            |   < ^₁ > < G >
     < G >  ->  < (₃ > < A > < )₃ >
            |   w
            |   x
            |   y
            |   z
     < (₀ > ->  (
     < (₁ > ->  (
     < (₂ > ->  (
     < (₃ > ->  (
     < )₀ > ->  )
     < )₁ > ->  )
     < )₂ > ->  )
     < )₃ > ->  )
     < +₀ > ->  +
     < +₁ > ->  +
     < -₀ > ->  -
     < -₁ > ->  -
     < *₀ > ->  *
     < *₁ > ->  *
     < /₀ > ->  /
     < /₁ > ->  /
     < %₀ > ->  %
     < %₁ > ->  %
     < ^₀ > ->  ^
     < ^₁ > ->  ^ }

3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >

G = ({A, A₀, B, B₀, B₁, C, C₀, D, D₀, D₁, D₂, E, E₀, F, F₀, G, G₀, (₀, (₁, (₂, (₃, )₀, )₁, )₂, )₃, +₀, +₁, -₀, -₁, *₀, *₁, /₀, /₁, %₀, %₁, ^₀, ^₁}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < G > < F >
            |   < (₀ > < A₀ >
            |   w
            |   x
            |   y
            |   z
     < A₀ > ->  < A > < )₀ >
     < B >  ->  < +₀ > < B₀ >
            |   < +₁ > < C >
            |   < -₀ > < B₁ >
            |   < -₁ > < C >
     < B₀ > ->  < C > < B >
     < B₁ > ->  < C > < B >
     < C >  ->  < E > < D >
            |   < G > < F >
            |   < (₁ > < C₀ >
            |   w
            |   x
            |   y
            |   z
     < C₀ > ->  < A > < )₁ >
     < D >  ->  < *₀ > < D₀ >
            |   < *₁ > < E >
            |   < /₀ > < D₁ >
            |   < /₁ > < E >
            |   < %₀ > < D₂ >
            |   < %₁ > < E >
     < D₀ > ->  < E > < D >
     < D₁ > ->  < E > < D >
     < D₂ > ->  < E > < D >
     < E >  ->  < G > < F >
            |   < (₂ > < E₀ >
            |   w
            |   x
            |   y
            |   z
     < E₀ > ->  < A > < )₂ >
     < F >  ->  < ^₀ > < F₀ >
            |   < ^₁ > < G >
     < F₀ > ->  < G > < F >
     < G >  ->  < (₃ > < G₀ >
            |   w
            |   x
            |   y
            |   z
     < G₀ > ->  < A > < )₃ >
     < (₀ > ->  (
     < (₁ > ->  (
     < (₂ > ->  (
     < (₃ > ->  (
     < )₀ > ->  )
     < )₁ > ->  )
     < )₂ > ->  )
     < )₃ > ->  )
     < +₀ > ->  +
     < +₁ > ->  +
     < -₀ > ->  -
     < -₁ > ->  -
     < *₀ > ->  *
     < *₁ > ->  *
     < /₀ > ->  /
     < /₁ > ->  /
     < %₀ > ->  %
     < %₁ > ->  %
     < ^₀ > ->  ^
     < ^₁ > ->  ^ }

Recomendamos

Clique Alimentos Agenda TI Revista Espírito Livre