Decidibilidade-Parte2

Prévia do material em texto

Decibilidade
Linguagem Turing-Reconhecível
Uma linguagem é Turing-reconhecível (ou L.R.E) sse existe MT 
que a reconhece.
Linguagem Turing-Decidível (ou Decidível)
Uma linguagem é Turing-decidível (ou L.Rec.) sse existe MT que 
a decide (pára sempre).
Descrição de MT
• Formal: contém detalhes do autômato (estados, alfabeto, fç. de 
transição, etc.)
• Informal: “pseudocódigo” descrevendo seu funcionamento
Decibilidade
Exemplo 
Seja MT M que decide A = { 02n | n ≥ 0} 
Descrição Informal de MT M
M = “Sobre a entrada w:
1. Faça uma varredura da esquerda para a direita na fita, marcando um 0 
não e outro, sim.
2. Se no passo 1, a fita continha um único 0, ACEITE.
3. Se no passo 1, a fita continha mais que um único 0 e o número de 0s era 
ímpar, REJEITE.
4. Retorne a cabeça para a extremidade esquerda da fita. 
5. Vá para o passo 1.”
Decibilidade
Exemplo 
Seja MT M que decide A = { 02n | n ≥ 0} 
Descrição Formal de MT M
q1 q2
q5
q3
qa
q4qr
0 / □, D 0 / x, D
□ / □, D
□ / □, D
x / x, D
x / x, D □ / □, D
0 / 0, E
□ / □, E
x / x, D
x / x, D
0 / x, D0 / 0, D
□ / □, D
x / x, E
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Discussão: AAFD = ?
Seja AFD B1 = ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1})
Se w1 = abaaba⇒ 〈 B1, w1 〉 ∈ AAFD
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), abaaba 〉 ∈ AAFD
Se w2 = abaab⇒ 〈 B1, w2 〉 ∉ AAFD
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), abaab 〉 ∉ AAFD
e1 e2
b b
a
a
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Discussão: (cont.)
AAFD = { 〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), λ 〉,
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), aa 〉, 
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), aaaa 〉, . . . ,
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), b 〉,
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), bb 〉, . . . ,
〈 ({e1,e2}, {a,b}, {[e1,a,e2], [e1,b,e1], [e2,a,e1], [e2,b,e2]}, e1, {e1}), abaaba 〉, . . . ,
. . . ,
〈 ({e1}, {a,b}, {[e1,a,e1], [e1,b,e1]}, e1, {e1}), babaaba 〉, . . . }
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Discussão: (cont.) 
Se considerarmos o alfabeto {0, 1}, então:
- Para cada estado e cada símbolo, seja R〈e1〉 = 1, R〈e1〉 = 12, R〈a〉 = 1, R〈b〉 = 12
- Para cada transição, seja R〈t〉 = R〈δ(e, s) = e´〉 = R〈e〉0R〈s〉R〈e´〉, s ∈ Σ, e, e´ ∈ Q
- Para conjunto estados finais, seja R〈F〉 = R〈f1〉0R〈f2〉0 ... 0R〈f|F|〉, fi ∈ F
- Seja R〈AFD B〉 = 1|Q|01|ΣΣΣΣ|00R〈t1〉00R〈t2〉00 ... 00R〈t|δδδδ|〉00R〈qi〉00R〈F〉
Logo R〈B1〉 = 120120010101200101201001201010012012012001001
- Seja w1 = abaaba⇒ R〈w1〉 = R〈a〉0R〈b〉0R〈a〉0R〈a〉0R〈b〉0R〈a〉 = 1012010101201
Então 〈B1,w1〉 = R〈B1〉000R〈w1〉 ∈ AAFD, ou ainda, 
120120010101200101201001201010012012012001001000 1012010101201 ∈ AAFD
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Discussão: (cont.)
AAFD = {120120010101200101201001201010012012012001001000,
120120010101200101201001201010012012012001001000101, 
1201200101012001012010012010100120120120010010001010101, . . . ,
12012001010120010120100120101001201201200100100012,
12012001010120010120100120101001201201200100100012012, . . . ,
120120010101200101201001201010012012012001001000 1012010101201, . . . ,
. . . ,
10120010101001012010010010001201012010101201, . . . }
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Ideia da Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Ideia da Prova:
MT M〈 B, w 〉
SIM ⇔⇔⇔⇔ w ∈∈∈∈ L(B)
NÃO ⇔⇔⇔⇔ w ∉∉∉∉ L(B)
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Ideia da Prova:
MT M〈 B, w 〉
SIM ⇔⇔⇔⇔ w ∈∈∈∈ L(B)
NÃO ⇔⇔⇔⇔ w ∉∉∉∉ L(B)
Similar a MT 
Universal
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈 B, w 〉 | B é AFD que aceita a entrada w }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFDs): 
AAFD = { 〈B, w 〉 | B é AFD que aceita a entrada w }
Prova: Seja MT M que decide AAFD
M = “Sobre a entrada 〈B, w 〉 em que B é AFD e w uma cadeia qualquer:
1. Simule B sobre a entrada w.
2. Se a simulação de B termina em um estado de aceitação, ACEITE; 
caso contrário, REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFNs): 
AAFN = { 〈 B, w 〉 | B é AFN que aceita a entrada w }
Ideia da Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFNs): 
AAFN = { 〈 B, w 〉 | B é AFN que aceita a entrada w }
Ideia da Prova:
MT N〈 B, w 〉
SIM ⇔⇔⇔⇔ w ∈∈∈∈ L(B)
NÃO ⇔⇔⇔⇔ w ∉∉∉∉ L(B)
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFNs): 
AAFN = { 〈 B, w 〉 | B é AFN que aceita a entrada w }
Ideia da Prova:
MT N〈 B, w 〉
SIM ⇔⇔⇔⇔ w ∈∈∈∈ L(B)
NÃO ⇔⇔⇔⇔ w ∉∉∉∉ L(B)
?
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFNs): 
AAFN = { 〈 B, w 〉 | B é AFN que aceita a entrada w }
Ideia da Prova:
MT N
SIM ⇔⇔⇔⇔ w ∈∈∈∈ L(B)
〈 B, w 〉
NÃO ⇔⇔⇔⇔ w ∉∉∉∉ L(B)
MT
Redutora
MT M〈 C, w 〉
SIM ⇔⇔⇔⇔ w ∈∈∈∈ L(C)
NÃO ⇔⇔⇔⇔ w ∉∉∉∉ L(C)
AAFD
AAFN
AFN→→→→ AFD
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFNs): 
AAFN = { 〈B, w 〉 | B é AFN que aceita a entrada w }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para AFNs): 
AAFN = { 〈B, w 〉 | B é AFN que aceita a entrada w }
Prova: Seja MT N que decide AAFN
N = “Sobre a entrada 〈 B, w 〉 em que B é AFN e w uma cadeia qualquer:
1. Converta AFN B para um AFD C equivalente.
2. Execute MT M que decide AAFD sobre a entrada 〈C, w 〉.
3. Se M aceitar, ACEITE; caso contrário, REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para Expressões Regulares): 
AEXR = { 〈 R, w 〉 | R é Expr. Regular que gera a sentença w }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Aceitação (para Expressões Regulares): 
AEXR = { 〈 R, w 〉 | R é Expr. Regular que gera a sentença w }
Prova: Seja MT P que decide AEXR
P = “Sobre a entrada 〈 R, w 〉 em que R é expr. regular e w uma cadeia qualquer:
1. Converta Expr. regular R para um AFN A equivalente.
2. Execute MT N que decide AAFN sobre a entrada 〈 A, w 〉.
3. Se N aceitar, ACEITE; caso contrário, REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Vacuidade: 
VAFD = { 〈 A 〉 | A é AFD e L(A) = ∅ }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Vacuidade: 
VAFD = { 〈 A 〉 | A é AFD e L(A) = ∅ }
Prova: Seja MT T que decide VAFD
T = “Sobre a entrada 〈 A 〉 em que A é AFD:
1. Marque o estado inicial de A.
2. Repita até que nenhum estado novo venha a ser marcado:
a. Marque qualquer estado que tenha uma transição chegando nela a 
partir de um estado que já está marcado.3. Se nenhum estado de aceitação estiver marcado, ACEITE; caso 
contrário, REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Equivalência: 
EQAFD = { 〈 A, B 〉 | A e B são AFDs e L(A) = L(B) }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Regulares
Problema da Equivalência: 
EQAFD = { 〈 A, B 〉 | A e B são AFDs e L(A) = L(B) }
Prova: Seja MT F que decide EQAFD
F = “Sobre a entrada 〈 A, B 〉 em que A e B são AFDs:
1. Construa AFD C tal que L(C) = (L(A) ∩ L(B)) ∪ (L(A) ∩ L(B)).
2. Execute MT T que decide VAFD sobre a entrada 〈C 〉.
3. Se T aceitar, ACEITE; caso contrário, REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Livres de Contexto
Problema da Aceitação (para GLCs): 
AGLC = { 〈G, w 〉 | G é GLC que gera a sentença w }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Livres de Contexto
Problema da Aceitação (para GLCs): 
AGLC = { 〈G, w 〉 | G é GLC que gera a sentença w }
Prova: Seja MT S que decide AGLC
S = “Sobre a entrada 〈G, w 〉 em que G é GLC e w uma sentença qualquer:
1. Converta a GLC G para um gramática equivalente na forma normal de 
Chomsky (FNC).
2. Liste todas as derivações com 2n - 1 passos, em que n é o tamanho da 
entrada w, exceto se n = 0, caso em que se deve listar todas as 
derivações com 01 (um) passo.
3. Se alguma das derivações gerar w, ACEITE; caso contrário, REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Livres de Contexto
Problema da Vacuidade: 
VGLC = { 〈G 〉 | G é GLC e L(G) = ∅ }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Livres de Contexto
Problema da Vacuidade: 
VGLC = { 〈G 〉 | G é GLC e L(G) = ∅ }
Prova: Seja MT R que decide VGLC
R = “Sobre a entrada 〈G 〉 em que G é GLC:
1. Marque todos os símbolos terminais em G.
2. Repita até que nenhuma variável nova venha a ser marcada:
a. Marque qualquer variável A para qual G possua uma regra A →
U1U2...Uk e que cada símbolo U1, U2, ..., Uk já tenha sido marcado.
3. Se a variável de partida não está marcada, ACEITE; caso contrário, 
REJEITE.”
Decibilidade
Problemas Decidíveis sobre Linguagens Livres de Contexto
Problema da Equivalência: 
EQGLC = { 〈G, H 〉 | G e H são GLCs e L(G) = L(H) }
Prova:
Decibilidade
Problemas Decidíveis sobre Linguagens Livres de Contexto
Problema da Equivalência: 
EQGLC = { 〈G, H 〉 | G e H são GLCs e L(G) = L(H) }
Prova: ???
Não é possível construir AP K tal que L(K) = (L(G) ∩ L(H)) ∪ (L(G) ∩ L(H)).
Por quê ???
Na verdade, EQGLC é indecidível !!!
Indecibilidade
Problemas Indecidíveis
Problema da Aceitação para MTs: (vulgarmente chamado Problema da Parada)
AMT = { 〈M, w 〉 | M é MT e M aceita a entrada w }
Obs: AMT é indecidível, mas AMT é Turing-reconhecível. 
U = “Sobre a entrada 〈M, w 〉 em que M é MT e w uma cadeia qualquer:
1. Simule M sobre a entrada w.
2. Se M em algum momento entra em um estado de aceitação, ACEITE; 
se M em algum momento entra em um estado de rejeição, REJEITE.”
Uma linguagem é decidível sse ela for Turing - reconhecível e co-Turing-
reconhecível (se ela for complemento de ling. Turing-reconhecível).
⇒ AMT não é Turing-reconhecível (senão AMT seria decidível).
Redutibilidade
Redução de Problema de Decisão para Outro
Se PD P é redutível a um PD Q decidível então P é decidível
Se PD P indecidível é redutível a um PD Q então Q é indecidível
SIM
NÃO
MT 
para PD 
Q
YRedução 
R
X
MT para PD P
Indecibilidade
Problemas Indecidíveis
Problema da “Parada” : 
PARAMT = { 〈M, w 〉 | M é MT e M pára sobre a entrada w }
Prova:
Indecibilidade
Problemas Indecidíveis
Problema da “Parada” : 
PARAMT = { 〈M, w 〉 | M é MT e M pára sobre a entrada w }
Prova: Suponha que exista MT R que decide PARAMT, logo poderíamos 
construir MT S que decide AMT da seguinte forma:
S = “Sobre a entrada 〈M, w 〉 em que M é MT e w uma cadeia qualquer :
1. Execute MT R sobre a entrada 〈M, w 〉.
2. Se R rejeita, REJEITE.
3. Se R aceita, simule MT M sobre a entrada w até que ela pare.
4. Se M aceitou, ACEITE; caso contrário, REJEITE.”
Logo, se MT R que decide PARAMT, então MT S que decide AMT. Como AMT é
indecidível, isto é um absurdo e PARAMT também deve ser indecidível.
Indecibilidade
Problemas Indecidíveis
Problema da Vacuidade: 
VMT = { 〈M 〉 | M é MT e L(M) = ∅ }
Prova:
Indecibilidade
Problemas Indecidíveis
Problema da Vacuidade: 
VMT = { 〈M 〉 | M é MT e L(M) = ∅ }
Prova: Suponha que exista MT R que decide VMT, logo poderíamos construir 
MT S que decide AMT da seguinte forma:
S = “Sobre a entrada 〈M, w 〉 em que M é MT e w uma cadeia qualquer :
1. Construa a seguinte MT M1:
M1 = “Sobre a entrada x:
a. Se x ≠ w, REJEITE.
b. Se x = w, execute M sobre a entrada w e aceite se M aceita w.”
2. Execute MT R sobre a entrada 〈 M1 〉.
3. Se R aceita, REJEITE; se R rejeita, ACEITE.”
Logo, se MT R que decide VMT, então MT S que decide AMT. Como AMT é
indecidível, isto é um absurdo e VMT também deve ser indecidível.
Indecibilidade
Problemas Indecidíveis
Problema da Regularidade: 
REGULARMT = { 〈M 〉 | M é MT e L(M) é um linguagem regular }
Prova:
Indecibilidade
Problemas Indecidíveis
Problema da Regularidade: 
REGULARMT = { 〈M 〉 | M é MT e L(M) é um linguagem regular }
Prova: Suponha que exista MT R que decide REGULARMT, logo poderíamos 
construir MT S que decide AMT da seguinte forma:
S = “Sobre a entrada 〈M, w 〉 em que M é MT e w uma cadeia qualquer :
1. Construa a seguinte MT M2:
M2 = “Sobre a entrada x:
a. Se x tem a forma 0n1n, ACEITE.
b. Se x não tem essa forma, execute M sobre a entrada w e aceite 
se M aceita w.”
2. Execute MT R sobre a entrada 〈 M2 〉.
3. Se R aceita, ACEITE; se R rejeita, REJEITE.”
Logo, se MT R que decide REGULARMT, então MT S que decide AMT. Como 
AMT é indecidível, isto é um absurdo e REGULARMT deve ser indecidível.
Indecibilidade
Problemas Indecidíveis
Problema da Equivalência: 
EQMT = { 〈 M1, M2 〉 | M1 e M2 são MTs e L(M1) = L(M2) }
Prova:
Indecibilidade
Problemas Indecidíveis
Problema da Equivalência: 
EQMT = { 〈 M1, M2 〉 | M1 e M2 são MTs e L(M1) = L(M2) }
Prova: Suponha que exista MT R que decide EQMT, logo poderíamos construir 
MT S que decide VMT da seguinte forma:
S = “Sobre a entrada 〈M 〉 em que M é MT :
1. Execute MT R sobre a entrada 〈M, M1 〉 em que M1 é um MT que 
rejeita todas as entradas.
2. Se R aceita, ACEITE; se R rejeita, REJEITE.”
Logo, se MT R que decide EQMT, então MT S que decide VMT. Como VMT é
indecidível, isto é um absurdo e EQMT também deve ser indecidível.
Indecibilidade
Propriedade Trivial 
Uma propriedade P de LREs é trivial se for satisfeita por toda LRE 
ou por nenhuma.
Exemplos de propriedades não triviais – considerando que M é uma MT qualquer
• Determinar se λ ∈ L(M) − Problema da Fita em Branco
• Determinar se L(M) contém alguma palavra (L(M) ≠ ∅)
• Determinar se L(M) contém todas as palavras em Σ* (L(M) = Σ*)
• Determinar se L(M) é finita
• Determinar se L(M) é regular
• Determinar se L(M) contém palavra iniciada com 0
Teorema de Rice
Se P é uma propriedade não trivial de LREs, então o problema 
Lr = { 〈M 〉 | L(M) satisfaz P} é indecidível (Lr não é recursiva).
Reduções via Histórias de Computação
História de Computação de Aceitação 
Uma história de computação de aceitação para MT M sobre uma entrada 
w é uma seqüência de configurações C1, C2, ..., CA, em que C1 é a 
configuração inicial, CA é uma configuração de aceitação, e cada Ci
segue legitimamente Ci-1 conforme a função de transição de M.
História de Computação de Rejeição 
Uma história de computação de rejeição para MT M sobre uma entrada w 
é uma seqüência de configurações C1, C2, ..., CR, em que C1 é a 
configuração inicial, CR é uma configuração de rejeição, ecada Ci
segue legitimamente Ci-1 conforme a função de transição de M.
⇒Histórias de computação são seqüências finitas
⇒Se M não pára sobre w então não existe história de comp. de M sobre w
⇒Máq. determinísticas têm no máximo uma história de comp. sobre uma dada 
entrada, enquanto que máq. não-determinísticas podem ter muitas histórias
Decibilidade × Indecibilidade − ALLs
ALLs são bastante poderosos, apesar de sua restrição de memória.
Os decisores de AAFD, AGLC, VAFD, VGLC são na verdade ALLs.
Obs.: Toda LLC pode ser decidida por um ALL !
Não é fácil obter ling. decidível que não pode ser decidida 
por um ALL !
Lema: Seja M um ALL com q estados e g símbolos no alfabeto de 
fita. Existem exatamente qngn configurações distintas de M para 
uma fita de tamanho n. (Por quê ?)
Decibilidade − ALLs
Problema Decidível sobre Linguagem Sensível ao Contexto
Problema da Aceitação (para ALLs): 
AALL = { 〈 B, w 〉 | B é ALL que aceita a entrada w }
Prova:
Decibilidade − ALLs
Problema Decidível sobre Linguagem Sensível ao Contexto
Problema da Aceitação (para ALLs): 
AALL = { 〈 B, w 〉 | B é ALL que aceita a entrada w }
Prova: Seja MT M que decide AALL
M = “Sobre a entrada 〈 B, w 〉 em que M é ALL e w uma cadeia qualquer:
1. Simule B sobre a entrada w por qngn passos ou até que ela pare.
2. Se B não parou em qngn passos, REJEITE.
3. Se B parou em estado de aceitação, ACEITE; caso contrário, 
REJEITE.”
Indecibilidade − ALLs
Problema Indecidível sobre Linguagem Sensível ao Contexto
Problema da Vacuidade (para ALLs): 
VALL = { 〈 B 〉 | B é ALL e L(B) = ∅ }
Ideia da Prova:
• Para uma MT M e uma entrada w, podemos determinar se M aceita w 
construindo um certo ALL B e testando se L(B) é vazia.
• A linguagem que B reconhece compreende todas as histórias de computação 
de aceitação para M sobre w.
• Se M aceita w, então essa linguagem contém uma cadeia e, portanto, não é
vazia; caso contrário, essa linguagem é vazia (pois M não aceita w).
• Logo se pudermos determinar se a linguagem de B é vazia, então podemos 
determinar se M aceita w.
PERGUNTA: Como construir o ALL B a partir de M e w ?
Indecibilidade − ALLs
PERGUNTA: Como construir o ALL B a partir de M e w ?
Resposta:
• Suponha que uma história de computação de aceitação seja representada por 
uma única cadeia em que as configurações são separadas por #.
• O ALL B funciona da seguinte forma. Primeiro, B quebra sua entrada x nas
cadeias C1, C2, ..., CA usando os delimitadores #.
• Em seguida, B determina/verifica se Ci satisfaz as 3 condições de uma 
história de computação de aceitação (COMO !?):
1. C1 é a configuração inicial de M sobre w; 
2. Cada Ci+1 segue legitimamente de Ci; e
3. CA é uma configuração de aceitação para M.
# # # # . . . # #
C1 C2 C3 CA
Indecibilidade − ALLs
Problema Indecidível sobre Linguagem Sensível ao Contexto
Problema da Vacuidade (para ALLs): 
VALL = { 〈 B 〉 | B é ALL e L(B) = ∅ }
Prova:
Indecibilidade − ALLs
Problema Indecidível sobre Linguagem Sensível ao Contexto
Problema da Vacuidade (para ALLs): 
VALL = { 〈 B 〉 | B é ALL e L(B) = ∅ }
Prova: Suponha que exista MT R que decide VALL, logo poderíamos construir 
MT S que decide AMT da seguinte forma:
S = “Sobre a entrada 〈M, w 〉 em que M é MT e w uma sentença qualquer:
1. Construir o ALL B que aceita uma história de computação de aceitação 
para M sobre w.
2. Execute MT R sobre a entrada 〈 B 〉.
3. Se R rejeita, ACEITE; se R aceita, REJEITE.”
Logo, se MT R que decide VAll, então MT S que decide AMT. Como AMT é
indecidível, isto é um absurdo e VALL também deve ser indecidível.
Indecibilidade
Problema Indecidível sobre Linguagem Livre de Contexto
Problema da Totalidade (para GLCs): 
TODASGLC = { 〈G 〉 | G é GLC e L(G) = Σ* }
Ideia da Prova: (Similar a prova para VALL)
• Para uma MT M e uma entrada w, podemos determinar se M aceita w 
construindo uma certa GLC G que gera todas as cadeias sse M não aceita w.
• Se M aceita w, então G não gera uma cadeia específica (a história de comp. 
de aceitação para M sobre w). Ou ainda, G é projetada para gerar todas as 
cadeias que não são histórias de computação de aceitação para M sobre w.
• G gera todas as cadeias que:
1. não começam com C1; 
2. não terminam com uma configuração de aceitação; ou
3. em que algum Ci+1 não se original legitimamente de Ci.
Indecibilidade
Problema Indecidível sobre Linguagem Livre de Contexto
Problema da Totalidade: TODASGLC = { 〈G 〉 | G é GLC e L(G) = Σ* }
Ideia da Prova: (continuação)
• Se M não aceita w, nenhuma história de comp. de aceitação existe, portanto, 
todas as cadeias falham de uma maneira ou outra. Conseqüentemente, G iria 
gerar todas as cadeias, como desejado.
• Construção de G a partir de um APN D, que verificará não-deterministica-
mente cada uma das três condições.
• As duas primeiras condições são facilmente verificáveis.
• Para verificar a terceira condição o APN D deverá empilha Ci para testar Ci+1, 
para isto, ser possível as configurações em posições pares serão escritas em 
ordem reversa, isto é :
# # # # # . . . # #
C1 C2R C3 CAC4R
→→ ← ←
Indecibilidade
Problema da Correspondência de Post (PCP)
• Dada uma coleção de dominós em que cada um contém duas cadeias 
• O PCP consiste em determinar se uma dada coleção de dominós possui um 
emparelhamento (lista de dominós em que a cadeia formada pelos símbolos da parte 
superior dos dominós é igual a cadeia formada pelos símbolos da parte inferior –
repetições são permitidas).
• Exemplo :
• Nem toda coleção possui um emparelhamento:
b
ca
a
ab
ca
a
abc
c
b
ca
a
ab
ca
a
abc
c
a
ab
acc
ba
ca
a
abc
c
Indecibilidade – PCP (Formalizando)
Sistema de Correspondência de Post (SCP)
Um SCP é um par (Σ, P), em que Σ é um alfabeto e P uma sequência finita de 
pares (x, y) tal que x, y ∈ Σ+. 
Emparelhamento (ou Solução) de um SCP
Seja um SCP S = (Σ, [(x1, y1), (x2, y2), . . ., (xn, yn)]), então um emparelhamento 
(ou solução) para S é uma sequência i1, i2, . . ., ik tal que 
xi1 xi2 . . . xik= yi1 yi2 . . . yik , 
em que 1 ≤ ij≤ n para 1 ≤ j ≤ k.
Exemplo: Seja o SCP S = ({0, 1}, [(10, 0), (0, 010), (01, 11)]). Esse SCP possui 
03 pares: (x1 = 10, y1 = 0), (x2 = 0, y2 = 010), (x3 = 01, y3 = 11). Uma solução 
seria a sequência 2131, pois x2 x1 x3 x1 = y2 y1 y3 y1, ou 0 10 01 10 = 010 0 11 0. 
Para maior clareza é conveniente se representar cada par (xi, yi) na forma .xi
yi
Indecibilidade – PCP (Formalizando)
Problema da Correspondência de Post (PCP)
O PCP consiste em determinar se uma dada coleção de dominós P possui ou não 
um emparelhamento
Formalizando através de uma linguagem:
PCP = { 〈 P〉 | P é um SCP e possui um emparelhamento }
OBS: PCP é indecidível.
t1
b1
t2
b2
tn
bn
• • •P = , , ,
R〈〈〈〈 P’ 〉〉〉〉Redução 
R’
R〈〈〈〈M, w 〉〉〉〉 Redução 
R’’
R〈〈〈〈 P 〉〉〉〉
AMT PCPM PCP
Indecibilidade – PCP (Formalizando)
Problema da Correspondência de Post Modificado (PCPM)
O PCPM consiste em determinar se uma dada coleção de dominós P’ possui ou 
não um emparelhamento que começa com o primeiro dominó .
Formalizando através de uma linguagem:
PCPM = { 〈 P’〉 | P’ é um SCP e possui um emparelhamento que começa com o 
primeiro dominó }
Ideia da Prova:
• Suponha que MT R decide o PCP e construa MT S que decide AMT (o que é
absurdo), isto é, S constrói uma instância do PCP P que tem um solução sse
M aceita w.
• Primeiramente, MT S constrói uma instância P’ do PCPM (em 07 passos).
• Em seguida, MT S converte P’ em uma instância P do PCP.
t1
b1
Indecibilidade – PCP (Formalizando)
Conversão:AMT→ PCPM
Passo 1:
• Inserir em P’ como primeiro dominó .
Passo 2:
• Para todo a, b ∈ Γ e todo q, r ∈ Q em que q ≠ qrejeita, se δ(q, a) = [r, b , D], 
inserir em P’. 
Passo 3:
• Para todo a, b, c ∈ Γ e todo q, r ∈ Q em que q ≠ qrejeita, se δ(q, a) = [r, b , E], 
inserir em P’. 
t1
b1
# 
# q0w1w2 . . . wn #
q a
b r
c q a
r c b
Indecibilidade – PCP (Formalizando)
Conversão: AMT→ PCPM (cont.)
Passo 4:
• Para todo a ∈ Γ, inserir em P’. 
Passo 5:
• Inserir e em P’.
Passo 6:
• Para todo a ∈ Γ, inserir e em P’. 
Passo 7:
• Inserir em P’. 
a qaceita
qaceita
#
#
#
���� #
qaceita a
qaceita
qaceita # #
#
a
a
Indecibilidade – PCP (Formalizando)
Exemplo de Conversão: AMT→ PCPM
• Seja Γ = { 0, 1, 2, �}, w = 0100 e que o estado inicial de M seja q0.
• Suponha que a MT M ao ler 0 no estado q0 vai para o estado q7 escrevendo 2 
na fita e movendo para direita, isto é, δ(q0, 0) = [ q7, 2, D]
• O passo 1 coloca o seguinte dominó em P’ :
• O passo 2 coloca o seguinte dominó em P’ :
• O passo 4 coloca os seguintes dominós em P’ : , , e 
q0 0
2 q7 
t1
b1
# 
# q0 0 1 0 0 #
=
0
0
1
1
2
2
����
����
Indecibilidade – PCP (Formalizando)
Exemplo de Conversão: AMT→ PCPM (cont.)
• Dessa forma o emparelhamento começaria com:
#
# q0 0 1 0 0 #
• Isso juntamente com os passos 2, 4 e 5 nos permitiria estendê-lo para:
# q0 0 1 0 0 #
# q0 0 1 0 0 # 2 q7 1 0 0 #
• Suponha que a MT M ao ler 1 no estado q7 vai para o estado q5 escrevendo 0 
na fita e movendo para direita, isto é, δ(q7, 1) = [q5, 0, D] e que ao ler 0 no 
estado q5 vai para o estado q9 escrevendo 2 na fita e movendo para esquerda, 
isto é, δ(q5, 0) = [q9, 2, E]. 
Indecibilidade – PCP (Formalizando)
Exemplo de Conversão: AMT→ PCPM (cont.)
• Dessa forma, o emparelhamento anterior se estenderia para:
# 2 q7 1 0 0 # 
# 2 q7 1 0 0 # 2 0 q5 0 0 #
• Como, δ(q5, 0) = [q9, 2, E], então teríamos: , , e 
• Então, o emparelhamento se estenderia ainda mais para:
# 2 0 q5 0 0 # 
# 2 0 q5 0 0 # 2 q9 0 2 0 #
• • •
• • •
0 q5 0
q9 0 2
1 q5 0
q9 1 2
2 q5 0
q9 2 2
���� q5 0
q9 ���� 2
Indecibilidade – PCP (Formalizando)
Exemplo de Conversão: AMT→ PCPM (cont.)
• Dessa forma emparelhamento corresponde a simulação de M sobre w, até qaceita :
#
# 2 1 qACEITA 0 2 #
• Usam-se os dominós do passo 6 para eliminar símbolos adjacentes a qaceita
• Dessa forma o emparelhamento se estenderia ainda mais para:
# 2 1 qACEITA 0 2 # #
# 2 1 qACEITA 0 2 # 2 1 qACEITA 2 # # qACEITA #
• • •
• • • • • •
Indecibilidade – PCP (Formalizando)
Exemplo de Conversão: AMT→ PCPM (cont.)
• Finalmente, usa-se o dominó do passo 7 para encerra o emparelhamento:
# qACEITA # #
# qACEITA # #
• P’ é uma instância do PCPM na qual o emparelhamento corresponde a uma 
simulação de M sobre w.
• Se considerarmos P’ uma instância de PCP (ao invés de PCPM) ele tem 
sempre um emparelhamento independentemente de se M pára sobre w ou não.
• Deve converter P’ em um instância P do PCP que ainda corresponda a uma 
simulação de M sobre w.
• • •
Indecibilidade – PCP (Formalizando)
Conversão: PCPM → PCP
Se a instância do PCPM P’ for:
Fazemos com que a instância correspondente do PCP P seja:
em que para uma cadeia qualquer u = u1u2 . . . uk (de tamanho k), temos que:
�u = *u1 * u2 * . . . * uk , isto é, adiciona-se * antes de cada símbolo de u
u� = u1 * u2 * . . . * uk * , isto é, adiciona-se * depois de cada símbolo de u
�u� = *u1 * u2 * . . . * uk * , isto é, adiciona-se * antes e depois de cada símbolo
t1
b1
t2
b2
tn
bn
• • •P’ = , , ,
����t1
b1����
����t2
b2����
����tn
bn����
• • •P = , , ,
����t1
����b1����
,
* ♦
♦
,