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

Exercício 08.35

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

Notação Algébrica:

G = ({S, A, B, C}, {a, b}, P, S)
P = {S → AB | BC
     A → AB | a
     B → AA | CB | a
     C → a | b}

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

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

Solução do Exercício

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

A gramática livre do contexto já está simplificada.

G = ({S, A, B, C}, {a, b}, P, S)
P = {S → AB | BC
     A → AB | a
     B → AA | CB | a
     C → a | b}

2. Renomeação das variáveis em uma ordem crescente qualquer

G = ({A, B, C, D}, {a, b}, P, S)
P = {A → BC | CD
     B → BC | a
     C → BB | DC | a
     D → a | b}

4. Exclusão das recursões da forma A_r → A_rα

G = ({A, B, B1, C, D}, {a, b}, P, S)
P = {A  → BC | CD
     B  → aB1 | a
     B1 → CB1 | C
     C  → BB | DC | a
     D  → a | b}

3. Transformação de produções para a forma A_r → A_sα, onde r ≤ s

G = ({A, B, B1, C, D}, {a, b}, P, S)
P = {A  → BC | CD
     B  → aB1 | a
     B1 → CB1 | C
     C  → aB1B | aB | DC | a
     D  → a | b}

5. Um terminal no início do lado direito de cada produção

G = ({A, B, B1, C, D}, {a, b}, P, S)
P = {A  → aB1C | aC
        | aB1BD | aBD | aCD | bCD | aD
     B  → aB1 | a
     B1 → aB1BB1 | aBB1 | aCB1 | bCB1 | aB1
        | aB1B | aB | aC | bC | a 
     C  → aB1B | aB | aC | bC | a
     D  → a | b}

6. Produções da forma A → aα onde α é composto por variáveis

G = ({A, B, B1, C, D}, {a, b}, P, S)
P = {A  → aB1C | aC
        | aB1BD | aBD | aCD | bCD | aD
     B  → aB1 | a
     B1 → aB1BB1 | aBB1 | aCB1 | bCB1 | aB1
        | aB1B | aB | aC | bC | a 
     C  → aB1B | aB | aC | bC | a
     D  → a | b}