P2_2021_2

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
DEPARTAMENTO DE INFORMÁTICA
Curso de Engenharia de Computação
2a. Avaliação de Algoritmos e Fundamentos da Teoria de Computação (INF09268) – 24/02/2022
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) Considere uma linguagem L, definida sobre o alfabeto Σ = {a, b}, aonde todas as strings pos-
suem sempre o mesmo número de a’s e b’s, em qualquer ordem. (Temos então, por exemplo, que abba ∈ L.)
Qual é o tipo de L segundo a Hierarquia de Chomsky (HC)? Justifique sua resposta projetando e apresen-
tando uma máquina abstrata M que reconhece L, aonde M deve possuir o mı́nimo poder de computação
necessário para reconhecer a linguagem. (Isto é, M deve estar no mesmo nı́vel/linha que L na HC.)
Q2 (1.0 ponto) Já vimos na disciplina que o Problema da Parada (Halting Problem) para máquinas de Turing
é indecidı́vel. Vimos também que às vezes é possı́vel simplificar um problema para torná-lo decidı́vel, ou
pelo menos semi-decidı́vel.
Considere agora o Problema Lambda, que consiste em decidir se uma máquina de Turing arbitrária M
para (halts) quando a sua computação é iniciada com uma fita vazia. Este problema é claramente um caso
particular do Problema da Parada, já que ele só se preocupa com a questão da parada da máquina M quando
a entrada é a string nula λ.
O Problema Lambda é decidı́vel, semi-decidı́vel ou indecidı́vel? Justifique adequadamente sua resposta.
Q3 (1.0 ponto) Construa uma DTM multi-fita que lê um número de entrada x em representação binária e es-
creve (converte) este mesmo número x em representação unária em uma outra fita, de saı́da. Determine
a complexidade assintótica de tempo da sua máquina. Obs.: Você pode apresentar a sua máquina tanto
como um diagrama de estados ou como um algoritmo, como preferir. Também é possı́vel utilizar mais fitas
auxiliares, se você quiser. Independente das escolhas, a resposta dada para a complexidade da máquina
deve ser bem justificada.
1