Exercício 08.05

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

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

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, A}
4	{D, F, A, C}
5	{D, F, A, C, E}
6	{D, F, A, C, E, G}
7	{D, F, A, C, E, G}

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

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

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

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