Turing

Fundamentos Teóricos da Computação
Trabalho – Máquina de Turing

Instruções: este trabalho poderá ser desenvolvido em duplas e está dividido em duas partes: entrega de material e apresentação da simulação das máquinas
Produto a ser entregue: as respectivas máquinas de Turing para cada exercício, postadas no webfólio da disciplina
Produto a ser apresentado em aula: as máquinas desenvolvidas rodando em um simulador
Data de entrega/apresentação: 20 de junho em laboratório
No acervo da turma (página da disciplina) há vários simuladores da máquina de Turing. O grupo deverá escolher aquele(s) que desejar para realizar as simulações de suas máquinas, ou ainda utilizar outro de sua escolha. Estas mesmas simulações, que mostram que suas máquinas funcionam deverão ser apresentadas na data marcada.

1.

Construa Máquinas de Turing que aceitem as seguintes linguagens:
a) L={w | w tem o mesmo número de símbolos a e b}
b) L= {wwr | w é palavra de {a,b}* e wr é a palavra reversa de w}

2. Encontre uma máquina de Turing que, dada uma fita inicial contendo uma cadeia não vazia de algarismos iguais a 1, marca o final da fita com um * e coloca uma cópia da cadeia à direita do *.
3. Encontre uma máquina de Turing que calcule a função f(n)=2n
4. Desenvolva uma máquina de Turing que realize as seguintes operações:
a) A-B : subtração de números inteiros definida por: m – n, se m > n zero, caso contrário
c) { w | o sexto símbolo da direita para esquerda é a}
5. Considere a Máquina de Turing representada através da tabela de transição de estados a seguir.
Verifique qual o estado final após a computação para as seguintes palavras: ab aba
aaba