Exercício 08.02

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

G = ({S, X, Y, Z, W}, {a, b, c}, P, S)
P = {< S >  ->  a < X > b
            |   < X > < Y >
            |   < W > a
     < X >  ->  ε
            |   < Y > < X > a
     < Y >  ->  < W > a
            |   < Z > a c
     < Z >  ->  < S > < Y > a
            |   < W > b < Z >
            |   < X >
     < W >  ->  a < X > 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	{X}
2	{X, Z}
3	{X, Z, W}
4	{X, Z, W}

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

G = ({S, X, Y, Z, W}, {a, b, c}, P, S)
P = {< S >  ->  a < X > b
            |   a b
            |   < X > < Y >
            |   < Y >
            |   < W > a
            |   a
     < X >  ->  < Y > < X > a
            |   < Y > a
     < Y >  ->  < W > a
            |   a
            |   < Z > a c
            |   a c
     < Z >  ->  < S > < Y > a
            |   < W > b < Z >
            |   < W > b
            |   b < Z >
            |   b
            |   < X >
     < W >  ->  a < X > c
            |   a c
            |   < Z > }

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

G = ({S, X, Y, Z, W}, {a, b, c}, P, S)
P = {< S >  ->  a < X > b
            |   a b
            |   < X > < Y >
            |   < Y >
            |   < W > a
            |   a
     < X >  ->  < Y > < X > a
            |   < Y > a
     < Y >  ->  < W > a
            |   a
            |   < Z > a c
            |   a c
     < Z >  ->  < S > < Y > a
            |   < W > b < Z >
            |   < W > b
            |   b < Z >
            |   b
            |   < X >
     < W >  ->  a < X > c
            |   a c
            |   < Z > }