Exercício 08.38

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

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

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}, P, S)
P = {< S >  ->  < B > < B >
            |   < B > < C >
            |   b
     < A >  ->  < A > < C >
            |   < C > < A >
            |   a
     < B >  ->  < B > < B >
            |   a
     < C >  ->  < B > < C >
            |   < C > < A >
            |   a }

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

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

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

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

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

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

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

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

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

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