Prova1_-_Victor_e_Marco1

Prévia do material em texto

Marco Antônio Milaneze Oliari e Victor Aguiar Marques
Q1
A base numérica escolhida para ser utilizada na máquina é a unária.
A passagem de estado para q1 faz a leitura do primeiro branco da fita. Nos estados
q1, q2 e q3, realiza-se a leitura dos dois primeiros 1’s da fita, e caso estes não
existam a máquina fica presa no estado em loop infinito. Isso ocorre pois quando
temos menos de três 1’s como entrada, a condição de x >= 2 não é atendida. No
estado q4 lê-se todos os 1’s restantes da fita, até que encontra-se um branco no
final e troca-se para o estado q5. Na transição para q6 e q7 substitui-se os dois
últimos 1’s por branco, realizando a subtração por 2. Em q7 lê-se os últimos 1’s para
a esquerda, lendo branco na posição 0 da fita e encerrando em q8.
Q2
A ideia dessa máquina é verificar se x > y, caso seja, ela usa a máquina G para
realizar a operação x - y, caso contrário, ela retorna 0. A base utilizada é a unária, a
máquina precisa de duas entradas separadas por um branco para funcionar.
Primeiramente a máquina lê o branco do início da fita de leitura, depois entra em c0,
onde começará a checar se x > y ou não. Os estados ‘c’ são todos para fazer essa
checagem (a máquina troca os 1’s do primeiro número por “x”s e os do segundo por
“y”s até que não encontre mais 1’s em um dos dois números). Caso x > y, a
máquina entra no estado g0, onde troca todos os “y”s por 1’s e depois passa para
g1, onde troca todos os “x”s por 1’s, após isso a cabeça de leitura estará na posição
0 da fita para utilizar a máquina G e realizar a subtração. Caso y >= x, a máquina vai
para o estado le0, onde percorre a segunda string inteira até chegar num branco,
logo após isso, a máquina vai para o estado le1, onde apaga a segunda string
inteira, semelhantemente, le2 apaga a primeira string inteira e a cabeça de leitura
fica na posição 0. A máquina lê o branco da posição 0 da fita e vai para direita,
parando em z0, depois escreve 1 antes de ir pra z1 e parar na posição 0 da fita
(com um 0 como saída).
Q3
Para desenvolver a máquina que solucione nosso problema, utilizamos um modelo
de duas fitas, com aceite por estado final, onde somente uma das fitas recebe a
entrada.
A ideia dessa máquina é separar a entrada em substrings de formato abn e
comparar o número de “b”s de cada substring i com a próxima (i+1), caso ni < ni+1
as comparações continuam, senão a máquina para de funcionar.
Até o estado q2, a máquina realiza a leitura do primeiro “a” da fita principal,
registrando-o na fita auxiliar. Neste estado os “b”s da fita principal são consumidos,
sendo também marcados na segunda, realizando assim uma cópia da primeira
substring abn na segunda fita. Dessa forma, um novo “a” é encontrado na primeira
fita, enquanto a fita auxiliar é percorrida para trás até o início, em q3. A partir deste
momento, inicia-se a comparação da substring da fita auxiliar com a “próxima”, que
é avaliada na fita principal.
De q4 para q5 avançam-se as duas fitas após o “a” (sendo a principal um “bloco”
inciado por “a” a frente), e de q5 para q6 consome-se todos os “b”s alinhados entre
fitas. Caso encontre-se um “a” na fita principal em conjunto com um “b” na auxiliar, a
máquina é levada para o estado q8 (isso indica que a substring lida anteriormente é
menor que a próxima, portanto ni < ni+1) e encerra. Quando o número de “b”s nas
duas fitas é igual, a máquina é encerrada no estado q6 (configurando o caso em
que ni+1 = ni). Já quando ainda existem “b”s na principal e tem-se branco na auxiliar,
retorna-se para o estado q2 para copiar os “b”s restantes para a fita auxiliar e
inicia-se um novo ciclo de comparações.
Quando não há mais nada para ser lido na fita principal após uma comparação bem
sucedida, encerra-se a máquina em q7, aceitando a entrada.