Exercício 08.35

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

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

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 >  ->  < A > < B >
            |   < B > < C >
     < A >  ->  < A > < B >
            |   a
     < B >  ->  < A > < A >
            |   < C > < B >
            |   a
     < C >  ->  a
            |   b }

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

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

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

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

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

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

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

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

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

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