Prévia do material em texto

UNIVERSIDADE FEDERAL DE LAVRAS 
DEPARTAMENTO DE CIÊNCIAS DA COMPUTAÇÃO 
GCC​ 108 – Teoria da Computação 
Professor: Rafael S. Durelli 
 
Lista de Exercícios sobre Máquina de Turing 
Respostas 
 
1. Qual a linguagem reconhecida por ? Descreva, em ‘alto nível’ as principais M 
operações realizadas por essa máquina. 
 
 
 
 {a b | i }L = i 2i ≥ 0 
A máquina M pode reconhecer a cadeia vazia indo direto de q ​1 para q ​6​, ou ‘apaga’ um ‘a’, 
pula ‘a’s e ‘b’s até o final da entrada. Volta ao começo da cadeia apagando dois ‘b’s do final 
até o começo. Reinicia esse ciclo até apagar todos os ‘a’s e ‘b’s, um ‘a’ para dois ‘b’s. 
 
 
2. Construa uma máquina de Turing que reconheça a linguagem por estados finais.L 
 
 {a b a b |i≥0, j≥i}L = i j i j 
 
Vale lembrar que, para uma mesma linguagem podem existir diversas máquinas de Turing. 
Assim como para um problema podem existir diversos algoritmos. 
 
 
Exercício 4 
 
 
 
 
 
 
3. Altere a máquina de Turing da questão anterior para aceitar a mesma linguagem por 
parada. 
 
 
 
4. Defina a classe das linguagens recursivamente enumeráveis (LRE) e linguagens 
recursivas (LR). 
As LRE são caracterizadas por terem pelo menos uma máquina de Turing que irá parar e 
reconhecer todas as cadeias pertencentes à linguagem recursivamente enumerável. 
Essa máquina de Turing pode entrar em loop para cadeias que não pertencem à 
linguagem. É também chamada de ‘semi-decidível’. 
Já as LR são caracterizadas por terem pelos menos uma máquina de Turing que irá parar 
para todas as cadeias de entrada, aceitando as pertencentes à linguagem e 
rejeitando as que não pertencem. É também chamada de ‘decidível’ ou 
‘Turing-decidível’. 
 
 
5. Construa uma máquina de Turing de duas fitas que reconheça a linguagem .L 
 
 {a b c |i≥0}L = i i i 
 
 
 
 
6. Descreva informalmente como se dá a simulação de uma máquina de Turing não 
determinística em uma máquina de Turing determinística de três fitas 
Primeiro, para cada transição da MTND, deve-se numerar as transições considerando o 
maior grau (n) de não determinismo de algum par estado-símbolo. Os estados que 
não têm transições não determinísticas terão suas transições replicadas até n. 
Depois, constrói-se uma MT de 3 fitas M’ para simular a MTND, seguindo os passos a seguir: 
1- Uma sequência de k números entre 1 e n é gerada e escrita na fita 3 
2- A entrada da MTND, que está na fita 1, é copiada para a fita 2 
3- Seguindo a sequência de k números na fita 3, a computação da MTND é simulada 
na fita 2 
4- Se a computação parar, M’ também pára e aceita a cadeia 
5- Caso contrário, uma nova sequência é gerada e escrita na fita 3, o conteúdo da 
fita 2 é apagado é volta-se ao passo 2 
 
7. Explique em que consiste o não determinismo em máquinas de Turing. 
O não determinismo em uma MTND se dá pelas múltiplas possibilidades de computação 
para um mesmo par estado-símbolo. Isso não quer dizer que a computação é não 
determinística, mas que a solução está sendo apresentada de maneira compactada. 
Em uma implementação real, todas as possibilidades de computação da MTND 
seriam exploradas em sequência. 
Caso uma das computações da MTND seja bem sucedida e leve à aceitação da entrada, os 
casos de computações que levaram à rejeição não invalidam o aceite. 
 
8. Construa uma máquina de Turing que faça a enumeração de todas as cadeias sobre o 
alfabeto que sejam de tamanho ímpar.a}{ 
 
Veja o uso da fita 2 na geração das cadeias na fita 1 
 
9. Prove o seguinte teorema: “ é uma linguagem recursiva se, e somente se, puder L 
ser enumerada em ordem lexicográfica.” 
Vide livro do Sudkamp (3​a​ edição), página 288. 
 
10. Seja uma máquina de Turing defina por:M 
 
 
 
a. Trace a computação para a entrada bcaba 
q​0​BabcabB 
Bq​1​abcabB 
Baq​1​bcabB 
Babq​1​cabB 
Baq​2​bcabB 
Bq​2​aacabB 
q​2​BbacabB 
 
b. Desenhe o diagrama de estados de M 
 
 
c. Descreva o que faz essa máquina de Turing 
A máquina de Turing inverte os ‘a’s e ‘b’s que ocorrem antes do primeiro ‘c’