Exercício 08.45

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

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

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	{E}
2	{E, B, D}
3	{E, B, D, C}
4	{E, B, D, C}

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

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

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

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