Exercício 08.29

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d}, P, S)
P = {< S >  ->  a < A > b < B >
            |   c d < C >
            |   < E >
     < A >  ->  < A >
            |   < B > c
     < B >  ->  d < A >
            |   c < B > d c
     < C >  ->  a b < E > < D > d
            |   < E > a b c
            |   a c < D > b
     < D >  ->  < D > a c
            |   c < D > a
            |   a c d
     < E >  ->  a < B > b < A > c
            |   ε
     < F >  ->  < C > < C > 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 {E}
2 {E, S}
3 {E, S}

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

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

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

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

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

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

Fecho(S) = {E}

Fecho(A) = {A}

Fecho(B) = ∅

Fecho(C) = ∅

Fecho(D) = ∅

Fecho(E) = ∅

Fecho(F) = ∅

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d}, P, S)
P = {< S >  ->  a < A > b < B >
            |   c d < C >
            |   a < B > b < A > c
            |   ε
     < A >  ->  < B > c
     < B >  ->  d < A >
            |   c < B > d c
     < C >  ->  a b < E > < D > d
            |   a b < D > d
            |   < E > a b c
            |   a b c
            |   a c < D > b
     < D >  ->  < D > a c
            |   c < D > a
            |   a c d
     < E >  ->  a < B > b < A > c
     < F >  ->  < C > < C > 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 {C, D}
2 {C, D, S, F}
3 {C, D, S, F}
G = ({S, C, D, F}, {a, b, c, d}, P, S)
P = {< S >  ->  c d < C >
            |   ε
     < C >  ->  a b < D > d
            |   a b c
            |   a c < D > b
     < D >  ->  < D > a c
            |   c < D > a
            |   a c d
     < F >  ->  < C > < C > 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 {S}
1 {S, C} {c, d}
2 {S, C, D} {c, d, a, b}
3 {S, C, D} {c, d, a, b}
G = ({S, C, D}, {a, b, c, d}, P, S)
P = {< S >  ->  c d < C >
            |   ε
     < C >  ->  a b < D > d
            |   a b c
            |   a c < D > b
     < D >  ->  < D > a c
            |   c < D > a
            |   a c d }

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

G = ({S, C, D, A₀, A₁, A₂, A₃, A₄, A₅, B₀, B₁, B₂, C₀, C₁, C₂, C₃, C₄, C₅, D₀, D₁, D₂},
     {a, b, c, d}, P, S)
P = {< S >  ->  < C₀ > < D₀ > < C >
            |   ε
     < C >  ->  < A₀ > < B₀ > < D > < D₁ >
            |   < A₁ > < B₁ > < C₁ >
            |   < A₂ > < C₂ > < D > < B₂ >
     < D >  ->  < D > < A₃ > < C₃ >
            |   < C₄ > < D > < A₄ >
            |   < A₅ > < C₅ > < D₂ >
     < A₀ > ->  a
     < A₁ > ->  a
     < A₂ > ->  a
     < A₃ > ->  a
     < A₄ > ->  a
     < A₅ > ->  a            
     < B₀ > ->  b
     < B₁ > ->  b
     < B₂ > ->  b
     < C₀ > ->  c
     < C₁ > ->  c
     < C₂ > ->  c
     < C₃ > ->  c
     < C₄ > ->  c
     < C₅ > ->  c
     < D₀ > ->  d
     < D₁ > ->  d
     < D₂ > ->  d }

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

G = ({S, S₀, C, X₀, X₁, X₂, X₃, X₄, D, Y₀, Y₁, Y₂, A₀, A₁, A₂, A₃, A₄, A₅, B₀, B₁, B₂,
      C₀, C₁, C₂, C₃, C₄, C₅, D₀, D₁, D₂}, {a, b, c, d}, P, S)
P = {< S >  ->  < C₀ > < S₀ >
            |   ε
     < S₀ > ->  < D₀ > < C >
     < C >  ->  < A₀ > < X₁ >
            |   < A₁ > < X₂ >
            |   < A₂ > < X₄ >
     < X₀ > ->  < < D > < D₁ >
     < X₁ > ->  < B₀ > < X₀ >
     < X₂ > ->  < B₁ > < C₁ >
     < X₃ > ->  < D > < B₂ >
     < X₄ > ->  < C₂ > < X₃ >
     < D >  ->  < D > < Y₀ >
            |   < C₄ > < Y₁ >
            |   < A₅ > < Y₂ >
     < Y₀ > ->  < A₃ > < C₃ >
     < Y₁ > ->  < D > < A₄ >
     < Y₂ > ->  < C₅ > < D₂ >
     < A₀ > ->  a
     < A₁ > ->  a
     < A₂ > ->  a
     < A₃ > ->  a
     < A₄ > ->  a
     < A₅ > ->  a            
     < B₀ > ->  b
     < B₁ > ->  b
     < B₂ > ->  b
     < C₀ > ->  c
     < C₁ > ->  c
     < C₂ > ->  c
     < C₃ > ->  c
     < C₄ > ->  c
     < C₅ > ->  c
     < D₀ > ->  d
     < D₁ > ->  d
     < D₂ > ->  d }

Recomendamos

Revista Segurança Digital Copy Duolingo