Exercício 08.43

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

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

Resposta

1. Exclusão de Produções Vazias

1.1. Identificação das variáveis que constituem produções vazias

Conjunto de variáveis que constituem produções vazias
Iteração	Variáveis
0	∅
1	{D}
2	{D, F}
3	{D, F, B}
4	{D, F, B}

1.2. Exclusão das produções vazias da gramática

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

1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática

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

2. Exclusão de Produções da Forma < A > -> < B >

2.1. Construção dos fechos das variáveis

Fecho(A) = {C}

Fecho(B) = {D, A, C, F}

Fecho(C) = ∅

Fecho(D) = {A, C}

Fecho(E) = ∅

Fecho(F) = {D, A, C}

2.2. Exclusão das produções da forma < A > -> < B >

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