Tutoriais - Linguagens Formais e Autômatos
Tutoriais
Linguagens Formais e Autômatos

1. Ybadoo
2. Tutoriais
3. Linguagens Formais e Autômatos
4. Simplificação de Gramáticas Livre do Contexto (GLC)
5. Exercício 08.62

Exercício 08.62

Simplifique a gramática livre de contexto a seguir:

Notação Algébrica:

G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {A → Exy | zD
     B → DF | xCy
     C → xEB | FCz
     D → yCA | AFA | ε
     E → AzC | BEyz
     F → zAy | D | ACB}

Notação de Backus-Naur (BNF):

G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {<A> ::= <E>xy | z<D>
     <B> ::= <D><F> | x<C>y
     <C> ::= x<E><B> | <F><C>z
     <D> ::= y<C><A> | <A><F><A> | ε
     <E> ::= <A>z<C> | <B><E>yz
     <F> ::= z<A>y | <D> | <A><C><B>}

Solução do Exercício

1. Exclusão de Produções Vazias

1.1. Identificação das variáveis que constituem produções vazias

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

G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {A → Exy | zD | z
     B → DF | D | F | xCy
     C → xEB | xE | FCz | Cz
     D → yCA | AFA | AA
     E → AzC | BEyz | Eyz
     F → zAy | D | ACB | AC}

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

G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {A → Exy | zD | z
     B → DF | D | F | xCy
     C → xEB | xE | FCz | Cz
     D → yCA | AFA | AA
     E → AzC | BEyz | Eyz
     F → zAy | D | ACB | AC}

2. Exclusão de Produções da Forma A → B

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

Fecho(A) = ∅
Fecho(B) = {D, F}
Fecho(C) = ∅
Fecho(D) = ∅
Fecho(E) = ∅
Fecho(F) = {D}

2.2. Exclusão das produções da forma A → B

G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {A → Exy | zD | z
     B → DF | zAy | yCA | AFA | AA | ACB | AC | xCy
     C → xEB | xE | FCz | Cz
     D → yCA | AFA | AA
     E → AzC | BEyz | Eyz
     F → zAy | yCA | AFA | AA | ACB | AC}

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

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

G = ({A, B, D, F}, {x, y, z}, P, A)
P = {A → zD | z
     B → DF | zAy | AFA | AA
     D → AFA | AA
     F → zAy | AFA | AA}

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

G = ({A, D, F}, {y, z}, P, A)
P = {A → zD | z
     D → AFA | AA
     F → zAy | AFA | AA}