Exercício 08.01

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

G = ({S, A, B}, {a, b}, P, S)
P = {< S >  ->  < A > < B >
            |   a < B > < B >
            |   a < S > < B > a
     < A >  ->  a
            |   a < B >
            |   a < S > b
     < B >  ->  ε
            |   b < B >
            |   a < S > < B > }

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}

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

G = ({S, A, B}, {a, b}, P, S)
P = {< S >  ->  < A > < B >
            |   < A >
            |   a < B > < B >
            |   a < B >
            |   a
            |   a < S > < B > a
            |   a < S > a
     < A >  ->  a
            |   a < B >
            |   a < S > b
     < B >  ->  b < B >
            |   b
            |   a < S > < B >
            |   a < S > }

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

G = ({S, A, B}, {a, b}, P, S)
P = {< S >  ->  < A > < B >
            |   < A >
            |   a < B > < B >
            |   a < B >
            |   a
            |   a < S > < B > a
            |   a < S > a
     < A >  ->  a
            |   a < B >
            |   a < S > b
     < B >  ->  b < B >
            |   b
            |   a < S > < B >
            |   a < S > }