Baixe o app para aproveitar ainda mais
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}.
Compartilhar