T2teoria151 1

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL
FACULDADE DE INFORMÁTICA
CURSO: Bacharelado em Sistemas de Informação
DISCIPLINA: Teoria da Computação (SI)
T. 168 – Prof. Flávio Oliveira
Trabalho T2
A nota T1 de trabalhos práticos da disciplina será calculada pelos questionários disponibilizados no Moodle. A segunda nota consiste no trabalho aqui especificado, cujo objetivo é construir e testar, com ajuda da ferramenta JFLAP, uma Máquina de Turing multi-fita que simula o funcionamento de uma ULA rudimentar a nível de linguagem de máquina.
Referências: livro do Hopcroft, Ullman & Motwani, seção 8.6.2 e livro de
Lewis & Papadimitriou, seção 4.4.

Requisitos: o grupo (de até 2 alunos) deverá:
a) Construir uma máquina de Turing multifita com as características especificadas abaixo;
b) Elaborar pelo menos um caso de teste para cada instrução implementada; c) Elaborar um pequeno documento que explique em alto nível a máquina produzida (estratégias, algoritmos, alternativas, etc.) e os casos de teste.
A máquina a ser simulada possui as seguintes características:

FITA 1: RI - registrador de instruções. Armazena a instrução a ser executada (ver abaixo).
FITA 2 e 3: registradores X e Y. Toda a computação é centralizada nos registradores X e Y (veja instruções abaixo).
Formato e conjunto de operações. Todos os registradores (ou seja, todos os operandos das instruções) possuem o tamanho fixo de 4 bits. A fita 1 contém o código da instrução conforme abaixo.
1. 001 Xor: máquina coloca no registrador X o “ou exclusivo” (bitwise) entre X e Y.
2. 010 Add: máquina coloca no registrador X a soma em binário de X e
Y.
3. 011 Sub: máquina coloca no registrador X a subtração em binário de
X e Y.

A máquina deve possuir exatamente as fitas especificadas, na ordem acima. Se for necessário, pode-se incluir fitas auxiliares, mas as primeiras 3 devem ter o conteúdo especificado.
O trabalho pode ser feito em duplas. Devem ser entregues:



O arquivo (.jff) contendo a máquina;
O