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

Exercício 09.32

Desenvolva uma gramática linear à direita 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 → iB
     B → kC
     C → iD | iE
     D → iD | jD | kD | iE
     E → kF
     F → jG
     G → iH | iJ
     H → iH | jH | kH | jI
     I → iJ
     J → jK
     K → ε }