Exercício 08.41

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

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

Resposta

1. Simplificação da gramática livre do contexto

A gramática livre do contexto já está simplificada.

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

2. Renomeação das variáveis em uma ordem crescente qualquer

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

3. Transformação de produções para a forma < Ar > -> < As > α, onde r ≤ s

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

4. Exclusão das recursões da forma < Ar > -> < Ar > α

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

5. Um terminal no início do lado direito de cada produção

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

6. Produções da forma < Ar > -> a α onde α é composto por variáveis

G = ({A, B, C, C₁, D, D₁, X₀₁, X₀₂, X₀₃, X₀₄, X₀₅, X₀₆, X₀₇, X₀₈, X₀₉, X₁₀, X₁₁, X₁₂, X₁₃, X₁₄, X₁₅, X₁₆, X₁₇, X₁₈, X₁₉, X₂₀,
      X₂₁, X₂₂, X₂₃, X₂₄, X₂₅, X₂₆, X₂₇, X₂₈, X₂₉, X₃₀, X₃₁, X₃₂, X₃₃, X₃₄, X₃₅, X₃₆, X₃₇, X₃₈, X₃₉, X₄₀, X₄₁, X₄₂, X₄₃, X₄₄,
      X₄₅, X₄₆, X₄₇, X₄₈, X₄₉, X₅₀, X₅₁, X₅₂, X₅₃, X₅₄, X₅₅, X₅₆, X₅₇, X₅₈, X₅₉, X₆₀, X₆₁, X₆₂, Y₀₁, Y₀₂, Y₀₃, Y₀₄, Y₀₅, Y₀₆,
      Y₀₇, Y₀₈, Y₀₉, Y₁₀, Y₁₁, Y₁₂, Y₁₃, Y₁₄, Y₁₅, Y₁₆, Y₁₇, Y₁₈, Y₁₉, Y₂₀, Y₂₁, Y₂₂, Y₂₃, Y₂₄, Y₂₅, Y₂₆, Y₂₇, Y₂₈, Y₂₉, Y₃₀,
      Y₃₁, Y₃₂, Y₃₃, Y₃₄, Y₃₅, Y₃₆, Y₃₇}, {a, b, c}, P, A)
P = {< A >   ->  c < D₁ > < Y₀₁ > < C > < C > < X₀₁ > < C₁ > < B > < C > < Y₀₂ >
             |   c < C > < C > < X₀₂ > < C₁ > < B > < C > < Y₀₃ >
             |   a < C > < X₀₃ > < C₁ > < B > < C > < Y₀₄ >
             |   b < C₁ > < B > < C > < Y₀₅ >
             |   c < D₁ > < Y₀₆ > < C > < C > < X₀₄ > < B > < C > < Y₀₇ >
             |   c < Y₀₈ > < C > < C > < X₀₅ > < B > < C > < Y₀₉ >
             |   a < C > < X₀₆ > < B > < C > < Y₁₀ >
             |   b < B > < C > < Y₁₁ >
             |   c < Y₁₂ > < C > < C > < Y₁₃ >
             |   a < C > < Y₁₄ >
     < B >   ->  c < D₁ > < Y₁₅ > < C > < C > < X₀₇ > < C₁ > < B >
             |   c < C > < C > < X₀₈ > < C₁ > < B >
             |   a < C > < X₀₉ > < C₁ > < B >
             |   b < C₁ > < B >
             |   c < D₁ > < Y₁₆ > < C > < C > < X₁₀ > < B >
             |   c < Y₁₇ > < C > < C > < X₁₁ > < B >
             |   a < C > < X₁₂ > < B >
             |   b < B >
             |   c < Y₁₈ > < C >
             |   a
     < C >   ->  c < D₁ > < Y₁₉ > < C > < C > < X₁₃ > < C₁ >
             |   c < C > < C > < X₁₄ > < C₁ >
             |   a < C > < X₁₅ > < C₁ >
             |   b < C₁ >
             |   c < D₁ > < Y₂₀ > < C > < C > < X₁₆ >
             |   c < Y₂₁ > < C > < C > < X₁₇ >
             |   a < C > < X₁₈ >
             |   b
     < C₁ >  ->  c < D₁ > < Y₂₂ > < C > < C > < X₁₉ > < C₁ > < B > < C > < X₂₀ > < C₁ >
             |   c < C > < C > < X₂₁ > < C₁ > < B > < C > < X₂₂ > < C₁ >
             |   a < C > < X₂₃ > < C₁ > < B > < C > < X₂₄ > < C₁ >
             |   b < C₁ > < B > < C > < X₂₅ > < C₁ >
             |   c < D₁ > < Y₃₀ > < C > < C > < X₂₆ > < B > < C > < X₂₇ > < C₁ >
             |   c < Y₂₄ > < C > < C > < X₂₈ > < B > < C > < X₂₉ > < C₁ >
             |   a < C > < X₃₀ > < B > < C > < X₃₁ > < C₁ >
             |   b < B > < C > < X₃₂ > < C₁ >
             |   c < Y₂₅ > < C > < C > < X₃₃ > < C₁ >
             |   a < C > < X₃₄ > < C₁ >
             |   c < D₁ > < Y₂₆ > < C > < C > < X₃₅ > < C₁ > < B > < C > < X₃₆ >
             |   c < C > < C > < X₃₇ > < C₁ > < B > < C > < X₃₈ >
             |   a < C > < X₃₉ > < C₁ > < B > < C > < X₄₀ >
             |   b < C₁ > < B > < C > < X₄₁ >
             |   c < D₁ > < Y₂₇ > < C > < C > < X₄₂ > < B > < C > < X₄₃ >
             |   c < Y₂₈ > < C > < C > < X₄₄ > < B > < C > < X₄₅ >
             |   a < C > < X₄₆ > < B > < C > < X₄₇ >
             |   b < B > < C > < X₄₈ >
             |   c < Y₂₉ > < C > < C > < X₄₉ >
             |   a < C > < X₅₀ >
     < D >   ->  c < D₁ >
             |   c
     < D₁ >  ->  c < D₁ > < Y₃₀ > < C > < C > < X₅₁ > < C₁ > < B > < D₁ >
             |   c < C > < C > < X₅₂ > < C₁ > < B > < D₁ >
             |   a < C > < X₅₃ > < C₁ > < B > < D₁ >
             |   b < C₁ > < B > < D₁ >
             |   c < D₁ > < Y₃₁ > < C > < C > < X₅₄ > < B > < D₁ >
             |   c < Y₃₂ > < C > < C > < X₅₅ > < B > < D₁ >
             |   a < C > < X₅₆ > < B > < D₁ >
             |   b < B > < D₁ >
             |   c < Y₃₃ > < C > < D₁ >
             |   a < D₁ >
             |   c < D₁ > < Y₄₀ > < C > < C > < X₅₇ > < C₁ > < B >
             |   c < C > < C > < X₅₈ > < C₁ > < B >
             |   a < C > < X₅₉ > < C₁ > < B >
             |   b < C₁ > < B >
             |   c < D₁ > < Y₃₅ > < C > < C > < X₆₀ > < B >
             |   c < Y₃₆ > < C > < C > < X₆₁ > < B >
             |   a < C > < X₆₂ > < B >
             |   b < B >
             |   c < Y₃₇ > < C >
             |   a
     < X₀₁ > ->  b
     < X₀₂ > ->  b
     < X₀₃ > ->  b
     < X₀₄ > ->  b
     < X₀₅ > ->  b
     < X₀₆ > ->  b
     < X₀₇ > ->  b
     < X₀₈ > ->  b
     < X₀₉ > ->  b
     < X₁₀ > ->  b
     < X₁₁ > ->  b
     < X₁₂ > ->  b
     < X₁₃ > ->  b
     < X₁₄ > ->  b
     < X₁₅ > ->  b
     < X₁₆ > ->  b
     < X₁₇ > ->  b
     < X₁₈ > ->  b
     < X₁₉ > ->  b
     < X₂₀ > ->  b
     < X₂₁ > ->  b
     < X₂₂ > ->  b
     < X₂₃ > ->  b
     < X₂₄ > ->  b
     < X₂₅ > ->  b
     < X₂₆ > ->  b
     < X₂₇ > ->  b
     < X₂₈ > ->  b
     < X₂₉ > ->  b
     < X₃₀ > ->  b
     < X₃₁ > ->  b
     < X₃₂ > ->  b
     < X₃₃ > ->  b
     < X₃₄ > ->  b
     < X₃₅ > ->  b
     < X₃₆ > ->  b
     < X₃₇ > ->  b
     < X₃₈ > ->  b
     < X₃₉ > ->  b
     < X₄₀ > ->  b
     < X₄₁ > ->  b
     < X₄₂ > ->  b
     < X₄₃ > ->  b
     < X₄₄ > ->  b
     < X₄₅ > ->  b
     < X₄₆ > ->  b
     < X₄₇ > ->  b
     < X₄₈ > ->  b
     < X₄₉ > ->  b
     < X₅₀ > ->  b
     < X₅₁ > ->  b
     < X₅₂ > ->  b
     < X₅₃ > ->  b
     < X₅₄ > ->  b
     < X₅₅ > ->  b
     < X₅₆ > ->  b
     < X₅₇ > ->  b
     < X₅₈ > ->  b
     < X₅₉ > ->  b
     < X₆₀ > ->  b
     < X₆₁ > ->  b
     < X₆₂ > ->  b
     < Y₀₁ > ->  c
     < Y₀₂ > ->  c
     < Y₀₃ > ->  c
     < Y₀₄ > ->  c
     < Y₀₅ > ->  c
     < Y₀₆ > ->  c
     < Y₀₇ > ->  c
     < Y₀₈ > ->  c
     < Y₀₉ > ->  c
     < Y₁₀ > ->  c
     < Y₁₁ > ->  c
     < Y₁₂ > ->  c
     < Y₁₃ > ->  c
     < Y₁₄ > ->  c
     < Y₁₅ > ->  c
     < Y₁₆ > ->  c
     < Y₁₇ > ->  c
     < Y₁₈ > ->  c
     < Y₁₉ > ->  c
     < Y₂₀ > ->  c
     < Y₂₁ > ->  c
     < Y₂₂ > ->  c
     < Y₂₃ > ->  c
     < Y₂₄ > ->  c
     < Y₂₅ > ->  c
     < Y₂₆ > ->  c
     < Y₂₇ > ->  c
     < Y₂₈ > ->  c
     < Y₂₉ > ->  c
     < Y₃₀ > ->  c
     < Y₃₁ > ->  c
     < Y₃₂ > ->  c
     < Y₃₃ > ->  c
     < Y₃₄ > ->  c
     < Y₃₅ > ->  c
     < Y₃₆ > ->  c
     < Y₃₇ > ->  c }