ProblemasDecidiveis-MT-Aula 3 - Eliana

Prévia do material em texto

Problemas Decidíveis
(por uma MT) 
 
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
w
0 1 1 0
Código do
 autômato A
String w 
qa
qr
Se A aceita w
Se A não aceita w
 
Como provar que ADFA é decídivel?
• M= Na entrada <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
Código do
 autômato A
qa
qr
Se L(A) é vazia
Se L(A) não é vazia
 
Como provar que EDFA é decidivel? 
M = Na entrada <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
B
Código do
 autômato A
qa
qr
Se L(A) = L(B)
Se L(A)
Código do
 autômato B
L(B)
 
EQDFA é decídivel
• M = Na entrada <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
w
0 1 1 0
Código de
 Gramática
 livre do contexto G
String w 
qa
qr
Se G gera w
Se G não gera w
 
Como provar que AGLC é decídivel? 
M = Na entrada <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
Código de
 Gramática livre do contexto G
qa
qr
Se L(G) é vazia
Se L(G) não é vazia
 
Como provar que EGLC é decídivel? 
M = Na entrada <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
G’
Código da
 Gramática G
qa
qr
Se L(G) = L(G’)
Se L(G)
Código da
 Gramática 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
Indecidível
Emptyness (E) Decídivel Decídivel
Indecidível
Equivalência 
(EQ) Decídivel Indecídivel
Indecidível
 
Redução de Problemas: 
Reducidibilidade
Um problema de decisão em P é redutível a um problema em P’ 
se existe uma MT que para qualquer pi ∈ P gera um outro 
problema p’i ∈ P’.
A solução de p’i pode ser usada para resolver pi
Um problema novo pode ser reduzido a uma problema cuja 
solução já é conhecida ou que já possua um algoritmo para 
solucioná-la.
Se um problema P é não-decidível e P possui uma redução para 
P’ então P’ também é não decidível.
 
Reducidibilidade
Problema A
Redução
através de
uma MT
Problema B
 
Reducidibilidade
Sejam A e B dois problemas de decisão. Suponha, que é possível 
modificar “reduzir” o probelma A de tal forma que ele se porta 
como um caso do problema B.
Se A é indecidível (não-computável), então como A é um caso de 
B, conclui-se que B também é indecidível (não computável).
Se B é decidível (computável ) então, como A é um caso de B, 
conclui-se que A também e computável. 
Se A é decidível então como A é um caso de B, conclui-se que 
parte de B que pertençe a A e decidível, entretanto o restante de 
B não se pode garantir. 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18