Lista01Máquina de Turing

Prévia do material em texto

UNIVERSIDADE FEDERAL DE LAVRAS
DEPARTAMENTO DE CIÊNCIAS DA COMPUTAÇÃO
GCC 108 – Teoria da Computação
Professor: Maurício Souza
Lista de Exercícios sobre Máquina de Turing
1. Qual a linguagem reconhecida por ? Descreva, em ‘alto nível’ as principais𝑀
operações realizadas por essa máquina.
2. Construa uma máquina de Turing que reconheça a linguagem por estados finais.𝐿
𝐿 = {𝑎𝑖𝑏𝑗𝑎𝑖𝑏𝑗 |𝑖≥0, 𝑗≥𝑖}
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).
5. Construa uma máquina de Turing de duas fitas que reconheça a linguagem .𝐿
𝐿 = {𝑎𝑖𝑏𝑖𝑐𝑖 |𝑖≥0}
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
7. Explique em que consiste o não determinismo em máquinas de Turing.
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.{𝑎}
9. Prove o seguinte teorema: “ é uma linguagem recursiva se, e somente se, puder ser𝐿
enumerada em ordem lexicográfica.”
10. Seja uma máquina de Turing defina por:𝑀
a. Trace a computação para a entrada 𝑎𝑏𝑐𝑎𝑏
b. Desenhe o diagrama de estados de 𝑀
c. Descreva o que faz essa máquina de Turing