Exercício 08.31

Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática:

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

Resposta

a) Construção dos fechos das variáveis

Fecho(A) = {C, E}

Fecho(B) = {D}

Fecho(C) = {E}

Fecho(D) = ∅

Fecho(E) = ∅

Fecho(F) = {G, B, D}

Fecho(G) = {B, D}

b) Exclusão das produções da forma < A > -> < B >

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

Recomendamos

Duolingo cert.br Vida de Suporte