Exercício 08.03

Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática:

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

Resposta

a) 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}

b) Exclusão das produções vazias da gramática

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

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

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