Projeto de Teoria da Computação II - 4º Período

O projeto consiste em criar um código de uma maquina de Turing usando um simulador de maquinas de Turing para simular este código.Esta máquina será de apenas uma fita infinita tanto para esquerda quanto para a direita e de apenas uma cabeça, sem mais recursos adicionais.

LEIA COM ATENÇÃO OS DETALHES ABAIXO:   

• A codificação de uma Maquina de Turing(MT) é uma String da forma: T11T11T..., com cada transição "T" sendo separada por dois "1"s , sendo uma transição composta por:[estado atual].[próximo estado].[símbolo lido].[símbolo escrito].[movimento], onde o movimento indica se a cabeça se deslocará uma célula para a esquerda ou para a direita ou permanece na célula atual.Para os  campos estado atual e próximo estado , a codificação é a seguinte:0->0,00->1,000->2 e assim por diante.No campo movimento, a codificação é a seguinte: 0->permanece na célula, 00->desloca-se uma célula a esquerda, 000->desloca-se uma célula a direita.Nos campos restantes , temos que 0->Símbolo Branco, e qualquer outro símbolo que auxilie na construção dos algoritmos(veja letras a, b e c) fica a critério tanto da questão a ser feita como do aluno.Em outras palavras, os símbolos definidos para as letras a b e c, devem ser usados na entrada e na saída e o aluno fica livre para criar símbolos que não aparecem nem na entrada e nem na saída e podem ser usados no processamento(00000,000000....). A separação de cada campo, será dada por um "1". Exemplo de uma codificação para uma TM: 010100101000110101000101000. Observe que tal maquina possui apenas 2 transições, 1 estado e que troca 00 por 0,000 por 0 e se desloca sempre para a direita.
  
• O projeto consistira na resolução de três letras :
•  
• a)Faça uma TM que dados 2 números na entrada(apenas 2) calcule a soma deles(vale 30%);
•  
• b)Faça uma TM que dados 2 números na entrada(apenas 2) calcule produto deles(vale 30%);
•  
• c)Faça uma TM que simula o método Replace, ou seja, dadas 3 entradas X Y Z , substitua cada ocorrência de X em Z por Y percorrendo a fita da esquerda para a direita, ou seja, da linha de cima para a linha mais abaixo na entrada.Temos também que X , Y ou Z nunca serão cadeias vazias(vale 40%);
  
•  
•  
• As entradas serão compostas por 4 elementos em notação unária, representados apenas por " 0"s, da seguinte forma: 0->Símbolo Branco; 00->0(zero); 000->1(um); 0000->Separador de entradas;Note que os números são binários, apesar de estar em notação unária; Exemplo(10 + 1 = 2 + 1 = 3 = 11 ,note que cada digito esta em uma linha e que o digito mais significativo esta na primeira linha) para a letra "a":
• Entrada
• 000
• 00
• 0000
• 000
•  
• Saída
• 000
• 000
•  
•  
• Simulação de replace("01", "1", "000101010000101011111011"): Temos que a primeira entrada é 01 seguida de um separador, seguida da segunda entrada 1 seguida de um separador seguido da terceira entrada  "000101010000101011111 011".Observe que a cadeia a ser substituída, pode ser menor ,igual ou maior que a cadeia que a substituirá.Veja exemplo para a letra c:
• Entrada
• 00
  000
  0000
  000
  0000
  00
  00
  00
  000
  00
  000
  00
  000
  00
  00
  00
  00
  000
  00
  000
  00
  000
  000
  000
  000
  000
  00
  000
  000
•  
• Saída
• 00
  00
  000
  000
  000
  00
  00
  00
  000
  000
  000
  000
  000
  000
  000
  000
  000
  
• O simulador da TM pode ser encontrado em  http://www.cin.ufpe.br/~maas/teoria/sim.java assim como 2 exemplos para clarificar o funcionamento("teste1.in" e "teste2.in", junto com suas explicaçoes, "ExplicaTestes.txt").
•  
• Note que a saida é um metodo de sim.java que imprime a parte util da fita.Entenda por parte util a parte limitada por infinitos brancos a esquerda e a direita(Exemplo: ...0 | 0 | 00 | 000 | 00 |  0 | 00 | 0 | 0... , a parte util será  00 | 000 | 00 |  0 | 00 ) , portanto cabe ao aluno fazer com que a parte util seja apenas o resultado final  e não também o lixo residual dos calculos efetuados,portanto este procedimento estará escrito no próprio código da TM;
•  
• O aluno terá a até a meia noite do dia estabelecido pelo professor  para entregar o projeto via e-mail através de um arquivo em formato  txt  para   famv@cin.ufpe.br    com    o   Subject: "Projeto de Teoria2 - TM";Este .txt deverá ter como nome <login>ProjTeoria2.txt ( ex: famvProjTeoria2.txt).O arquivo txt, deverá ter o seguinte formato:
• letra a:codigo da TM da letra "a"
• letra b:codigo da TM da letra "b"
• letra c:codigo da TM da letra "c"
• Exemplo:
• letra a:01010010100011010100010100011010010000101000
  letra b:0101001010001101010001010001101001000010100
  letra c:01010010100011010100010100011010010000101000
•  
• NÃO ACEITAREMOS SOB HIPÓTESE ALGUMA ,O ENVIO DE OUTRO SIMULADOR PARA QUE SE POSSA RODAR AS TM´s . QUEREMOS SOMENTE OS CÓDIGOS DAS MAQUINAS NO FORMATO ESPECIFICADO ACIMA, QUEM MANDAR OUTRO SIMULADOR FICARÁ COM ZERO PORQUE FEZ O PROJETO FORA DA ESPECIFICAÇÃO.
•  
• Quaisquer dúvidas falar com os monitores FranciscoValadares (famv@cin.ufpe.br) ou Marcos Aurélio (maas@cin.ufpe.br).
•  
• Boa sorte a Todos!!!