Exercício 08.57

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

G = ({S, X, K, Y}, {x, y, z}, P, S)
P = {< S > ::= < K > < Y >
            |  < X > < K >
     < X > ::= < X > < K >
            |  x
     < K > ::= < Y > < K >
            |  < X > < X >
            |  x
     < Y > ::= y
            |  z }

Resposta

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

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

G = ({S, X, K, Y}, {x, y, z}, P, S)
P = {< S > ::= < K > < Y >
            |  < X > < K >
     < X > ::= < X > < K >
            |  x
     < K > ::= < Y > < K >
            |  < X > < X >
            |  x
     < Y > ::= y
            |  z }

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

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

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

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

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

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

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

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

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

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