2020 3-TeoriaDaComputacao-2VA

Prévia do material em texto

Avaliação de 2ª Unidade (PLE 2020.3)
Curso: Ciência da Computação Disciplina: Teoria da Computação
Profa: Maria Sibaldo
Aluno: Data: 22/10/2020
Orientações para a avaliação:
Obs.: LEMBREM-SE QUE A PROVA É SEM CONSULTA, E CASO ALGUÉM DESRESPEITE ALGUMA
RESTRIÇÃO TERÁ A NOTA AUTOMATICAMENTE COMO ZERO (0). 
1) (2,0 pontos) Desenvolva um autômato com pilha que aceite a seguinte linguagem:
a) L = {ai bj | i < j}, alfabeto {a, b}
2) (2,0 pontos) Desenvolva uma máquina de Turing que a aceite e que sempre pare
para qualquer entrada da linguagem abaixo.
a) Função transdutora que receba como entrada dois números: x e y (separados
por #) e verifique se x >= y ou se x < y. Para o primeiro caso a saída dele ser 1, para
o segundo deve ser 11.
Exemplos: (a) Entrada: 111#111, Saída: 1; (b) Entrada: 11#111, Saída 11.
3) Responda às questões abaixo:
a) (1,0 ponto) Cite a hipótese de Church, sua importância para a Ciência da
Computação e o porquê dela não ser demonstrável. 
b) (1,0 ponto) Reconhecer o complemento de uma linguagem pode ser impossível,
mesmo que seja possível reconhecer a linguagem. Por quê?
4) (1,0 ponto) Dada as alternativas abaixo, marque V para as afirmações verdadeiras e
F para as falsas. Justifique o porquê das afirmações serem falsas ou verdadeiras.
a) L é recursiva se e somente se L e ~L são recursivamente enumeráveis.
b) Se uma linguagem L sobre um alfabeto Σ qualquer é recursiva, então o seu
complemento ~L é recursiva.
c) A classe das Linguagens Recursivamente Enumeráveis está contida propriamente
na Classe das Linguagens Recursivas.
d) Computacionalmente existem mais problemas do que algoritmos para resolvê-
los.