Lista 1

Prévia do material em texto

Lista de Exercícios de Decibilidade e Indecidibilidade 
 
A lista de exercícios é individual é será entregue em formato manuscrito no inicio da 
aula. 
Data de Entrega: 09/05/2019 
 
1. Descreva formalmente a máquina de Turing que simule o autômato finito que 
reconhece as sentenças da expressão regular ab*a. 
2. Faça as máquinas de Turing decisoras das seguintes linguagens: 
a) L = {ambncm+n | n,m ≥ 0} 
b) L = {anbmanbm | n,m ≥ 0} 
c) L = {wwR | w é qualquer string de 0’s e 1’s} 
3. Responda a cada um dos itens abaixo para o AFD M e dê razões para suas respostas. 
 
a) 〈M, 0100〉 ∈ AAFD? 
b) 〈M, 011〉 ∈ AAFD? 
c) 〈M〉 ∈ AAFD? 
d) 〈M, 0100〉 ∈ AEXR? 
e) 〈M〉 ∈ VAFD? 
 
4. Seja INFINITAAFD = {〈A〉 | A é um AFD e L(A) é uma linguagem infinita}. Mostre 
que INFINITAAFD é decidível. 
5. Seja INFINITAAP = {〈M〉 | M é um AP e L(M) é uma linguagem infinita}. Mostre 
que INFINITAAP é decidível. 
6. Seja A = {〈M〉 | M é um AFD que não aceita nenhuma cadeia contendo um número 
ímpar de 1s. Mostre que A é decidível. 
7. Seja Σ = {0,1}. Mostre que o problema de se determinar se uma GLC gera alguma 
cadeia em 1* é decidível. Em outras palavras, mostre que 
{〈G〉 | G é uma GLC sobre {0,1} e 1* ⋂ L(G) ≠ ∅} 
é uma linguagem decidível. 
8. Seja A = {〈R,S〉 | R e S são expressões regulares e L(R) ⊆ L(S)}. Mostre que A é 
decidível. 
9. Um estado inacessível em uma máquina de Turing é um estado no qual a máquina 
nunca entra sobre qualquer que seja a entrada. Considere o problema de se determinar 
se uma máquina de Turing tem algum estado inacessível. Formule esse problema como 
uma linguagem e mostre que ela é indecidível. 
10. Seja INFINITAMT = {〈M〉 | M é uma MT e L(M) é uma linguagem infinita}. Mostre 
que INFINITAMT é indecidível. 
11. Considere o problema de se determinar se um máquina de Turing de duas fitas em 
algum momento escreve um símbolo não-branco sobre sua segunda fita quando ela é 
executada sobre a entrada w. Formule esse problema como uma linguagem e mostre que 
é indecidível. 
12. Seja EQMT = {〈M1,M2〉 | M1 e M2 são MTs e L(M1) = L(M2)}. Prove que é 
indecidível. 
13. Mostre que AMT não é redutível por mapeamento a VMT. Em outras palavras, mostre 
que nenhuma função computável reduz AMT a VMT. (Dica: Use uma prova por 
contradição, e fatos que você já conhece sobre AMT e VMT.) 
14. Considere o problema de determinar se um AP aceita alguma cadeia da forma {ww | 
w ∈ {0,1}*}. Use o método da historia de computação para mostrar que o problema é 
indecidível. 
15. Seja T = {〈M〉 | M é uma MT que aceita wR sempre que ela aceita w}. Mostre que T 
é indecidível. 
16. Mostre que o Problema da Correspondência de Post é decidível sobre o alfabeto 
unário ∑ = {1}.