P1_2021_2

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) – 16/12/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 (0.5 ponto) Uma função total f : N → N é crescente monótona se f(n) < f(n + 1) para todo n ∈ N.
Usando um argumento de diagonalização, mostre que existe um número incontável de funções crescentes
monótonas.
Q2 (0.8 ponto) Seja a linguagem descrita pela expressão regular (ab)∗ ∪ a∗. Pede-se:
a. Apresente os autômatos NFA-λ que aceitam as expressões regulares fundamentais a e b.
b. Partindo dos autômatos do item (a) e usando as construções do Teorema 5.5.3 (Sudkamp, pág. 168),
mostre passo-a-passo a elaboração do NFA-λ que reconhece a linguagem acima.
c. Usando o algoritmo de determinização (Algoritmo 5.6.3), apresente um DFA equivalente ao NFA-λ
do item b.
Q3 (0.9 ponto) Construa uma Máquina de Turing Padrão que computa a função sucessor s(n) = n + 1. A
diferença entre a máquina já vista nas aulas e a desta questão, é que aqui o número de entrada n está em
notação binária. Como sempre, a fita inicialmente contém um branco (B) na posição zero, seguido por n
em binário, e a cabeça começa na posição zero da fita. O bit mais à esquerda na fita (posição um) é o bit
mais significativo do número n.
Q4 (0.8 ponto) Construa uma Máquina de Turing com uma fita two-way (isto é, infinita nos dois sentidos), com
alfabeto de entrada Σ = {a}, que aceita por parada a linguagem definida pela expressão regular a+. Isto
é, a máquina para se a fita contém ao menos uma posição que não é branco. Por outro lado, se a entrada para
a máquina for uma fita vazia, a computação não termina nunca. É essencial considerar que o(s) sı́mbolo(s)
a pode(m) estar em qualquer lugar da fita, não necessariamente imediatamente à direita da posição inicial
da cabeça da fita.
1