p1

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
DEPARTAMENTO DE INFORMÁTICA
Curso de Engenharia de Computação
1a. Avaliação de Algoritmos e Fundamentos da Teoria de Computação (INF09268) – 15/07/2021
Prof. Eduardo Zambon
Nome: Nota:
Instruções:
• Esta avaliação parcial vale 3.0 pontos na média parcial da disciplina.
• Esta avaliação deve ser feita obrigatoriamente em dupla.
• Por se tratar de uma avaliação, assume-se que você só vai discutir as soluções com a sua dupla.
Obviamente, o formato deste semestre não facilita a aplicação dessa regra; esse ponto fica para a
ética e consciência de cada um.
• Envie um arquivo PDF com as suas respostas na tarefa do Classrom até o prazo limite.
• Faça um envio por dupla.
Q1 (1.0 ponto) Construa uma máquina de Turing que computa a função numérica parcial f : N ⇀ N, definida
como
f(x) =
{
x− 2 se x ≥ 2
↑ caso contrário.
Não utilize macros nessa questão: apresente o diagrama completo da máquina com todos os estados. Utilize
a base de representação numérica que preferir. Importante: Lembre-se que a sua máquina deve entrar em
loop para os valores aonde a função f é indefinida. Lembre-se também que nos casos em que a máquina
para, ela deve estar no estado final lendo branco na posição 0 da fita.
Q2 (1.0 ponto) Considere a existência de uma máquina G que computa a função parcial g : N×N ⇀ N,
definida como
g(x, y) =
{
x− y se x > y
↑ caso contrário.
Utilizando G, construa uma máquina de Turing que computa a função total h : N×N→N, definida como
h(x, y) =
{
x− y se x > y
0 caso contrário.
Você é livre para utilizar as macros e máquinas definidas entre as seções 9.2 e 9.4 do livro do Sudkamp na
sua resposta. Utilize a base de representação numérica que preferir. Obs.: Para garantir que o projeto da
sua máquina está correto, indique sempre a entrada e saı́da esperada de cada macro/máquina, usando a
notação vista no material de estudo.
Q3 (1.0 ponto) Seja o alfabeto Σ = {a, b}. Construa uma máquina de Turing que aceita strings aonde cada a é
seguido por um número crescente de b’s; isto é, as strings aceitas têm a forma
abn1abn2 . . . abnk , k > 1,
onde n1 < n2 < · · · < nk. Obs.: Você pode utilizar qualquer variante de TM que quiser, isto é, multi-faixa,
multi-fita, não-determinı́stica, etc.
1