Prova Fundamentos da Teoria da Computação

Prévia do material em texto

DCC/ICEx/UFMG
DCC 129 - Fundamentos de Teoria da Computação
1o semestre de 2021
Área de Teoria
Exame Especial
2020/11/05
Estudante: Matrícula:
Instruções:
i. Este exame possui 1 página(s). Verifique se sua cópia do exame está completa.
ii. Escreva seu nome na primeira página das suas respostas e forneça todas as suas respostas à mão. Não
serão aceitas respostas digitadas.
iii. Você tem 24 horas para concluir o exame e enviar suas respostas em um único arquivo PDF digitalizado
via a interface apropriada no Moodle do curso. Certifique-se de que o arquivo enviado esteja completamente
legível.
iv. Esta prova é sem consulta: você não tem permissão para consultar o livro texto, suas notas de aula, a Internet,
seus colegas ou quaisquer outras pessoas ou fontes para concluir o exame.
v. Se você acredita que alguma pergunta esteja subespecificada, anote as suposições que você teve que fazer para chegar
a sua resposta e justifique-as como parte de sua resposta à pergunta.
vi. Suas respostas serão avaliadas em sua clareza e concisão. Cada resposta deve ser completa e devidamente
justificada, e todas as etapas intermediárias de sua solução devem ser apresentadas com clareza.
1. (20% da nota) Responda às seguintes questões.
(a) Construa um AFD para {w ∈ {a, b}∗ | w não contém a subpalavra aba}, usando 4 estados.
(b) Construa um AFN para {w ∈ {a, b}∗ | w contém a subpalavra aba}, usando 4 estados.
(c) Dê uma expressão regular para a linguagem
{w ∈ {a, b}∗ | w tem pelo menos três símbolos, e o primeiro símbolo é diferente do terceiro.}
2. (20% da nota) Use o lema do bombeamento para linguagens regulares para mostrar que a linguagem
L1 = {akb2kc3k | k ≥ 0}
não é regular.
3. (20% da nota) Seja a linguagem
L2 = {aibj | i ≥ j + 2}.
(a) Exiba uma gramática livre-do-contexto que gere L2 usando no máximo 4 regras.
(b) Mostre o diagrama de estados de um autômato de pilha que reconheça L2 usando no máximo 6 estados. (Não
use o método-padrão de construir um AP com três estados. Projete seu AP especificamente para a linguagem
e sem usar atalhos!)
4. (20% da nota) Diga se cada afirmativa abaixo é verdadeira ou falsa. Justifique sua resposta de forma clara e
completa.
(a) A linguagem DEZGLC = {〈G〉 | G é uma gramática livre-do-contexto que só gera cadeias de tamanho 10} é
decidível.
(b) Todo problema indecidível tem necessariamente um número infinito de instâncias.
(c) Assuma que o PD A é redutível por mapeamento a um PD B. Então se B pode ser decidido por um autômato
com pilha, A também pode ser decidido por um autômato com pilha.
5. (20% da nota) Demonstre que se A e B são dois problemas decidíveis, então A ≤m B.
1