Problemas Decidíveis
Envolvendo Autômatos e
Linguagens Livres do Contexto
Problemas Clássicos
Autômato
Gramática
Aceitação (A)
Decídivel
Decídivel
Emptyness (E)
Decídivel
Decídivel
Equivalência
(EQ)
Decídivel
Indecídivel
Problema da Aceitação ADFA
A
qa
w
qr
0 11 0
Código do
autômato A
String w
Se A aceita w
Se A não aceita w
ADFA é decídivel
• M= No input <A,w> faça
1. Executa A no string w
2. Se A atinge um estado final, M pára em
qa.
3. Se A pára num estado não-final, M pára
em qr
Problema Emptyness EDFA
A
qa
qr
Código do
autômato A
Se L(A) é vazia
Se L(A) não é vazia
EDFA é decidivel
M = No input <A> faça
1. Marc := {q0}
2. Enquanto houver mudanças em Marc faça
- Insere em Marc todos os estados q tais
que δ(q’,a) = q para algum q’ em Marc.
3. Testa se Marc contém algum estado final
4. Se contém, pára em qr
5. Se não contém, pára em qa.
Problema da Equivalência EQDFA
A
qa
B
qr
Se L(A) = L(B)
Se L(A)
Código do
autômato A
Código do
autômato B
L(B)
EQDFA é decídivel
•
•
•
•
•
•
•
•
•
M = No input <A,B> faça
Construa autômato A’ complementar de A
Construa autômato B’ complementar de B
Construa autômato C = A intersecção B’
Construa autômato D = B intersecção A’
Construa autômato E = união de C e D
Execute a máquina M’ que decide o problema EDFA em
E
Se M’ pára em qa, M pára em qa
Se M’ pára em qr, M pára em qr
Problema da Aceitação AGLC
G
qa
w
qr
0 11 0
String w
Código de
Gramática
livre do contexto G
Se G gera w
Se G não gera w
AGLC é decídivel
M = No input <G,w> faça
1. Encontre G’ = Forma Normal de Chomsky de G
1. N := |w|
2. Crie todas as derivações de comprimento 2N 1 começando em S, pela gramática G’.
3. Se w é derivada numa destas derivações pára
em qa
4. Se w não é derivada em nenhuma destas
derivações pára em qr.
Problema Emptyness EGLC
G
qa
qr
Código de
Gramática livre do contexto G
Se L(G) é vazia
Se L(G) não é vazia
EGLC é decídivel
M = No input <G = (V,T,P,S) > faca
1. Marc := T
2. Enquanto houver mudanças em Marc faça
Insere em Marc todas as variáveis A tais que
existe regra A  B1…Bn com Bi em Marc para
todo i = 1,…,n
3. Testa se Marc contém a variável S
4. Se contém, pára em qr.
5. Se não contém, pára em qa.
Problema da Equivalencia EQGLC
G
qa
G’
qr
Código da
Código da
Gramática G Gramática G’
Se L(G) = L(G’)
Se L(G)
L(G’)
Problema da Equivalência EQGLC
• Problema indecídivel
• Não existe algoritmo que resolve este
problema !
Problemas Clássicos
Autômato
Gramática
Máquina de
Turing
Aceitação
(A)
Decídivel
Decídivel
Indecídivel
Emptyness
(E)
Decídivel
Decídivel
Indecídivel
Indecídivel
Indecídivel
Equivalência Decídivel
(EQ)
Turing-decidíveis
EDFA
EQTM
ADFA
EQDFA
AGLC
EQGLC
EQGLC
EGLC
ETM
ETM
EQTM
ATM
ATM
Turing-reconhecíveis