Baixe o app para aproveitar ainda mais
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 (3a edição), página 288. 10. Seja uma máquina de Turing defina por:M a. Trace a computação para a entrada bcaba q0BabcabB Bq1abcabB Baq1bcabB Babq1cabB Baq2bcabB Bq2aacabB q2BbacabB 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’
Compartilhar