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

Exercício 09.31

Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {i, j, k} que reconheça a linguagem L = {w | w possui iki como prefixo, ikji como subpalavra e jij como sufixo}.

Solução do Exercício

G = ({A, B, C, D, E, F, G, H, I, J, K}, {i, j, k}, P, A)
P = {A → Bj
     B → Ci | Ei
     C → Dj
     D → Di | Dj | Dk | Ei
     E → Fj
     F → Gk
     G → Hi | Ii
     H → Hi | Hj | Hk | Ii
     I → Jk
     J → Ki
     K → ε }