Exercício 08.55

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

G = ({A, B, C}, {x, y}, P, A)
P = { < A > ::= x < B >
             |  y < C > < C >
             |  x < A > < C > y
      < B > ::= y
             |  < C > x
             |  < C > < C >
      < C > ::= ε
             |  y < C >
             |  x < B > < 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	{C}
2	{C, B}
3	{C, B}

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

G = ({A, B, C}, {x, y}, P, A)
P = { < A > ::= x < B >
             |  x
             |  y < C > < C >
             |  y < C >
             |  y
             |  x < A > < C > y
             |  x < A > y
      < B > ::= y
             |  < C > x
             |  x
             |  < C > < C >
             |  < C >
      < C > ::= y < C >
             |  y
             |  x < B > < C >
             |  x < B >
             |  x < C >
             |  x }

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

G = ({A, B, C}, {x, y}, P, A)
P = { < A > ::= x < B >
             |  x
             |  y < C > < C >
             |  y < C >
             |  y
             |  x < A > < C > y
             |  x < A > y
      < B > ::= y
             |  < C > x
             |  x
             |  < C > < C >
             |  < C >
      < C > ::= y < C >
             |  y
             |  x < B > < C >
             |  x < B >
             |  x < C >
             |  x }