Exercício 08.28

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

G = ({A, B, C, D, E, F}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
     < B >  ->  + < C > < B >
            |   ε
     < C >  ->  < E > < D >
     < D >  ->  * < E > < D >
            |   ε
     < E >  ->  ( < A > )
            |   < F >
     < F >  ->  a
            |   b
            |   c }

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

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

G = ({A, B, C, D, E, F}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < C >
     < B >  ->  + < C > < B >
            |   + < C >
     < C >  ->  < E > < D >
            |   < E >
     < D >  ->  * < E > < D >
            |   * < E >
     < E >  ->  ( < A > )
            |   < F >
     < F >  ->  a
            |   b
            |   c }

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

G = ({A, B, C, D, E, F}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < C >
     < B >  ->  + < C > < B >
            |   + < C >
     < C >  ->  < E > < D >
            |   < E >
     < D >  ->  * < E > < D >
            |   * < E >
     < E >  ->  ( < A > )
            |   < F >
     < F >  ->  a
            |   b
            |   c }

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, F}

Fecho(B) = ∅

Fecho(C) = {E, F}

Fecho(D) = ∅

Fecho(E) = {F}

Fecho(F) = ∅

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

G = ({A, B, C, D, E, F}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   ( < A > )
            |   a
            |   b
            |   c
     < B >  ->  + < C > < B >
            |   + < C >
     < C >  ->  < E > < D >
            |   ( < A > )
            |   a
            |   b
            |   c
     < D >  ->  * < E > < D >
            |   * < E >
     < E >  ->  ( < A > )
            |   a
            |   b
            |   c
     < F >  ->  a
            |   b
            |   c }

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, F}
2	{A, C, E, F, B, D}
3	{A, C, E, F, B, D}

G = ({A, B, C, D, E, F}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   ( < A > )
            |   a
            |   b
            |   c
     < B >  ->  + < C > < B >
            |   + < C >
     < C >  ->  < E > < D >
            |   ( < A > )
            |   a
            |   b
            |   c
     < D >  ->  * < E > < D >
            |   * < E >
     < E >  ->  ( < A > )
            |   a
            |   b
            |   c
     < F >  ->  a
            |   b
            |   c }

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}	{(, ), a, b, c}
2	{A, C, B, E, D}	{(, ), a, b, c, +, *}

G = ({A, B, C, D, E}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   ( < A > )
            |   a
            |   b
            |   c
     < B >  ->  + < C > < B >
            |   + < C >
     < C >  ->  < E > < D >
            |   ( < A > )
            |   a
            |   b
            |   c
     < D >  ->  * < E > < D >
            |   * < E >
     < E >  ->  ( < A > )
            |   a
            |   b
            |   c }

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

G = ({A, B, C, D, E, X₀, Y₀, M₀, M₁, X₁, y₁, P₀, P₁, X₂, Y₂}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < X₀ > < A > < Y₀ >
            |   a
            |   b
            |   c
     < B >  ->  < M₀ > < C > < B >
            |   < M₁ > < C >
     < C >  ->  < E > < D >
            |   < X₁ > < A > < Y₁ >
            |   a
            |   b
            |   c
     < D >  ->  < P₀ > < E > < D >
            |   < P₁ > < E >
     < E >  ->  < X₂ > < A > < Y₂ >
            |   a
            |   b
            |   c
     < X₀ > ->  (
     < Y₀ > ->  )
     < M₀ > ->  +
     < M₁ > ->  +
     < X₁ > ->  (
     < Y₁ > ->  )
     < P₀ > ->  *
     < P₁ > ->  *
     < X₂ > ->  (
     < Y₂ > ->  ) }

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

G = ({A, A₀, B, B₀, C, C₀, D, D₀, E, E₀, X₀, Y₀, M₀, M₁, X₁, y₁, P₀, P₁, X₂, Y₂}, {a, b, c, +, *, (, )}, P, A)
P = {< A >  ->  < C > < B >
            |   < E > < D >
            |   < X₀ > < A₀ >
            |   a
            |   b
            |   c
     < A₀ > ->  < A > < Y₀ >
     < B >  ->  < M₀ > < B₀ >
            |   < M₁ > < C >
     < B₀ > ->  < C > < B >
     < C >  ->  < E > < D >
            |   < X₁ > < C₀ >
            |   a
            |   b
            |   c
     < C₀ > ->  < A > < Y₁ >
     < D >  ->  < P₀ > < D₀ >
            |   < P₁ > < E >
     < D₀ > ->  < E > < D >
     < E >  ->  < X₂ > < E₀ >
            |   a
            |   b
            |   c
     < E₀ > ->  < A > < Y₂ >
     < X₀ > ->  (
     < Y₀ > ->  )
     < M₀ > ->  +
     < M₁ > ->  +
     < X₁ > ->  (
     < Y₁ > ->  )
     < P₀ > ->  *
     < P₁ > ->  *
     < X₂ > ->  (
     < Y₂ > ->  ) }