Exercício 08.61

Simplifique a gramática livre de contexto:

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

Resposta

1. Exclusão de Produções Vazias

1.1. 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	{E}
2	{E, S}
3	{E, S}

1.2. Exclusão das produções vazias da gramática

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

1.3. 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}, P, S)
P = {< S >  ->  a < A > e < B >
            |   c d < C >
            |   < E >
            |   ε
     < A >  ->  < A >
            |   < B > c
     < B >  ->  d < A >
            |   c < B > d c
     < C >  ->  a b < E > < D > d
            |   a b < D > d
            |   < E > a b c
            |   a b c
            |   a c < D > b
     < D >  ->  < D > a c
            |   c < D > a
            |   a c d
     < E >  ->  a < B > e < A > c
     < F >  ->  < C > < C > c }

2. Exclusão de Produções da Forma < A > -> < B >

2.1. Construção dos fechos das variáveis

Fecho(S) = {E}

Fecho(A) = {A}

Fecho(B) = ∅

Fecho(C) = ∅

Fecho(D) = ∅

Fecho(E) = ∅

Fecho(F) = ∅

2.2. Exclusão das produções da forma < A > -> < B >

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

3. Exclusão de Símbolos Inúteis

3.1. Identificação das variáveis que constituem terminais

Conjunto de variáveis que constituem terminais
Iteração	Variáveis
0	∅
1	{C, D}
2	{C, D, S, F}
3	{C, D, S, F}

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

3.2. Identificação dos símbolos alcançáveis a partir do símbolo inicial

Conjunto de símbolos alcançáveis a partir do símbolo inicial
Iteração	Variáveis	Terminais
0	{S}	∅
1	{S, C}	{c, d}
2	{S, C, D}	{c, d, a, b}
3	{S, C, D}	{c, d, a, b}

G = ({S, C, D}, {a, b, c, d}, P, S)
P = {< S >  ->  c d < C >
            |   ε
     < C >  ->  a b < D > d
            |   a b c
            |   a c < D > b
     < D >  ->  < D > a c
            |   c < D > a
            |   a c d }