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

G = ({A, B, C, D}, {x, y, z}, P, A)
P = {< A >  ->  < D > x < D >
     < B >  ->  y
            |   < A > x
     < C >  ->  z z
            |   z < A > z
     < D >  ->  y < B >
            |   < B > x }

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

G = ({A, B, D}, {x, y}, P, A)
P = {< A >  ->  < D > x < D >
     < B >  ->  y
            |   < A > x
     < D >  ->  y < B >
            |   < B > x }

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

G = ({A, B, C}, {x, y}, P, A)
P = {< A >  ->  < C > x < C >
     < B >  ->  y
            |   < A > x
     < C >  ->  y < B >
            |   < B > x }

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

G = ({A, B, C}, {x, y}, P, A)
P = {< A >  ->  < C > x < C >
     < B >  ->  y
            |   < C > x < C > x
     < C >  ->  y < B >
            |   y x
            |   < C > x < C > x x }

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

G = ({A, B, C, C₀}, {x, y}, P, A)
P = {< A >  ->  < C > x < C >
     < B >  ->  y
            |   < C > x < C > x
     < C >  ->  y < B >
            |   y x
            |   y < B > < C₀ >
            |   y x < C₀ >
     < C₀ > ->  x < C > x x
            |   x < C > x x < C₀ > }

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

G = ({A, B, C, C₀}, {x, y}, P, A)
P = {< A >  ->  y < B > x < C >
            |   y x x < C >
            |   y < B > < C₀ > x < C >
            |   y x < C₀ > x < C >
     < B >  ->  y
            |   y < B > x < C > x
            |   y x x < C > x
            |   y < B > < C₀ > x < C > x
            |   y x < C₀ > x < C > x
     < C >  ->  y < B >
            |   y x
            |   y < B > < C₀ >
            |   y x < C₀ >
     < C₀ > ->  x < C > x x
            |   x < C > x x < C₀ > }

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

G = ({A, B, C, C₀, X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇, X₈, X₉, X₁₀, X₁₁, X₁₂, X₁₃, X₁₄, X₁₅, X₁₆, X₁₇, X₁₈,
      X₁₉, X₂₀, X₂₁}, {x, y}, P, A)
P = {< A >   ->  y < B > < X₀ > < C >
             |   y < X₁ > < X₂ > < C >
             |   y < B > < C₀ > < X₃ > < C >
             |   y < X₄ > < C₀ > < X₅ > < C >
     < B >   ->  y
             |   y < B > < X₆ > < C > < X₇ >
             |   y < X₈ > < X₉ > < C > < X₁₀ >
             |   y < B > < C₀ > < X₁₁ > < C > < X₁₂ >
             |   y < X₁₃ > < C₀ > < X₁₄ > < C > < X₁₅ >
     < C >   ->  y < B >
             |   y < X₁₆ >
             |   y < B > < C₀ >
             |   y < X₁₇ > < C₀ >
     < C₀ >  ->  x < C > < X₁₈ > < X₁₉ >
             |   x < C > < X₂₀ > < X₂₁ > < C₀ >
     < 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 }