Exercício 08.36

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

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

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

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

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

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

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

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

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

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

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

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

Recomendamos

Java Magazine Duolingo Revista Digital