Exercício 08.04

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d, e, f}, P, S)
P = {< S >  ->  a < A > a
            |   < A >
     < A >  ->  < B >
            |   c < C > < D > d
     < B >  ->  b < S > b b
            |   b
            |   ε
     < C >  ->  a a < A > a a
            |   < S >
     < D >  ->  < C > < D > d
            |   d < D >
     < E >  ->  < F > f
            |  < S > f < A > e
     < F >  ->  e < E > e
            |   f
            |   < B > c d < C > < 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	{B}
2	{B, A}
3	{B, A, S}
4	{B, A, S, C}
5	{B, A, S, C}

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d, e, f}, P, S)
P = {< S >  ->  a < A > a
            |   a a
            |   < A >
     < A >  ->  < B >
            |   c < C > < D > d
            |   c < D > d
     < B >  ->  b < S > b b
            |   b b b
            |   b
     < C >  ->  a a < A > a a
            |   a a a a
            |   < S >
     < D >  ->  < C > < D > d
            |   < D > d
            |   d < D >
     < E >  ->  < F > f
            |  < S > f < A > e
            |  < S > f e
            |  f < A > e
            |  f e
     < F >  ->  e < E > e
            |   f
            |   < B > c d < C > < D >
            |   < B > c d < D >
            |   c d < C > < D >
            |   c d < D > }

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d, e, f}, P, S)
P = {< S >  ->  a < A > a
            |   a a
            |   < A >
            |   ε
     < A >  ->  < B >
            |   c < C > < D > d
            |   c < D > d
     < B >  ->  b < S > b b
            |   b b b
            |   b
     < C >  ->  a a < A > a a
            |   a a a a
            |   < S >
     < D >  ->  < C > < D > d
            |   < D > d
            |   d < D >
     < E >  ->  < F > f
            |  < S > f < A > e
            |  < S > f e
            |  f < A > e
            |  f e
     < F >  ->  e < E > e
            |   f
            |   < B > c d < C > < D >
            |   < B > c d < D >
            |   c d < C > < D >
            |   c d < D > }