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

1. Ybadoo
2. Tutoriais
3. Linguagens Formais e Autômatos
4. Hierarquia de Chomsky
5. Exercício 09.30

Exercício 09.30

Apresente uma derivação para a sentença aaabbcccdd sobre a gramática a seguir.

Notação Algébrica:

G = ({S, A, B, X, Y}, {a, b, c, d}, P, S)
P = {S  → AB
     A  → aAX | aX
     B  → bBd | bYd
     Xb → bX
     XY → Yc
     Y  → ε }

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

G = ({S, A, B, X, Y}, {a, b, c, d}, P, S)
P = {<S>    ::= <A><B> 
     <A>    ::= a<A><X> | a<X>
     <B>    ::= b<B>d | b<Y>d
     <X>b   ::= b<X>
     <X><Y> ::= <Y>c
     <Y>    ::= ε }

Solução do Exercício

S                S  → AB
AB               A  → aAX
aAXB             A  → aAX
aaAXXB           A  → aX
aaaXXXB          B  → bBd
aaaXXXbBd        B  → bYd
aaaXXXbbYdd      Xb → bX
aaaXXbXbbYdd     Xb → bX
aaaXXbbXYdd      XY → Yc
aaaXXbbYcdd      Xb → bX
aaaXbXbYcdd      Xb → bX
aaaXbbXYcdd      XY → Yc
aaaXbbYccdd      Xb → bX
aaabXbYccdd      Xb → bX
aaabbXYccdd      XY → Yc
aaabbYcccdd      Y  → ε
aaabbcccdd