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.29

Exercício 08.29

Converta para a Forma Normal de Chomsky a gramática:

Notação Algébrica:

G = ({S, A, B, C, D, E, F}, {a, b, c, d}, P, S)
P = {S → aAbB | cdC | E
     A → A | Bc
     B → dA | cBdc
     C → abEDd | Eabc | acDb
     D → Dac | cDa | acd
     E → aBbAc | ε
     F → CCc}

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d}, P, S)
P = {<S> ::= a<A>b<B> | cd<C> | <E>
     <A> ::= <A> | <B>c
     <B> ::= d<A> | c<B>dc
     <C> ::= ab<E><D>d | <E>abc | ac<D>b
     <D> ::= <D>ac | c<D>a | acd
     <E> ::= a<B>b<A>c | ε
     <F> ::= <C><C>c}

Solução do Exercício

1. Simplificação da gramática livre do contexto

1.1. Exclusão de Produções Vazias

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

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d}, P, S)
P = {S → aAbB | cdC | E
     A → A | Bc
     B → dA | cBdc
     C → abEDd | abDd | Eabc | abc | acDb
     D → Dac | cDa | acd
     E → aBbAc
     F → CCc}

1.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}, P, S)
P = {S → aAbB | cdC | E | ε
     A → A | Bc
     B → dA | cBdc
     C → abEDd | abDd | Eabc | abc | acDb
     D → Dac | cDa | acd
     E → aBbAc
     F → CCc}

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

1.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) = ∅

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

G = ({S, A, B, C, D, E, F}, {a, b, c, d}, P, S)
P = {S → aAbB | cdC | aBbAc | ε
     A → Bc
     B → dA | cBdc
     C → abEDd | abDd | Eabc | abc | acDb
     D → Dac | cDa | acd
     E → aBbAc
     F → CCc}

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

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

G = ({S, C, D, F}, {a, b, c, d}, P, S)
P = {S → cdC | ε
     C → abDd | abc | acDb
     D → Dac | cDa | acd
     F → CCc}

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

G = ({S, C, D}, {a, b, c, d}, P, S)
P = {S → cdC | ε
     C → abDd | abc | acDb
     D → Dac | cDa | acd}

2. Conversão das produções contendo terminais para a forma A → a

G = ({S, C, D, W1, W2, W3, W4, W5, W6, X1, X2, X3, Y1, Y2, Y3, Y4, Y5, Y6, Z1, Z2, Z3}, {a, b, c, d}, P, S)
P = {S → Y1Z1C | ε
     C → W1X1DZ2 | W2X2Y2 | W3Y3DX3
     D → DW4Y4 | Y5DW5 | W6Y6Z3
     W1 → a
     W2 → a
     W3 → a
     W4 → a
     W5 → a
     W6 → a
     X1 → b
     X2 → b
     X3 → b
     Y1 → c
     Y2 → c
     Y3 → c
     Y4 → c
     Y5 → c
     Y6 → c
     Z1 → d
     Z2 → d
     Z3 → d}

3. Conversão das produções contendo variáveis para a forma A → BC

G = ({S, S1, C, C1, C2, C3, C4, C5, D, D1, D2, D3, W1, W2, W3, W4, W5, W6, X1, X2, X3, Y1, Y2, Y3, Y4, Y5, Y6, Z1, Z2, Z3}, {a, b, c, d}, P, S)
P = {S → Y1S1 | ε
     S1 → Z1C
     C → W1C2 | W2C3 | W3C5
     C1 → DZ2
     C2 → X1C1
     C3 → X2Y2
     C4 → DX3
     C5 → Y3C4
     D → DD1 | Y5D2 | W6D3
     D1 → W4Y4
     D2 → DW5
     D3 → Y6Z3
     W1 → a
     W2 → a
     W3 → a
     W4 → a
     W5 → a
     W6 → a
     X1 → b
     X2 → b
     X3 → b
     Y1 → c
     Y2 → c
     Y3 → c
     Y4 → c
     Y5 → c
     Y6 → c
     Z1 → d
     Z2 → d
     Z3 → d}