2VA - Teoria da Computação

Prévia do material em texto

Avaliação de 2ª unidade (PLE 2020.3) 
 
Disciplina: Teoria da Computação 
Profª: Maria Sibaldo 
Aluno: José Sávio Gama Macêdo 
 
1- 
 
 
 
 
 
 
 
 
q0 transição - lendo a, tendo z0, retira-se z0, volta z0 e empilha a 
q1 - lendo a, tendo a, retira-se a, volta a pra pilha e empilha a 
Transição de q1 pra q2 - lendo b, tendo a, retira-se a (empilha-se vazio) 
q2 - lendo b, tendo a, retira-se a (empilha-se vazio) 
Transição de q2 pra f - lendo b, tendo z0, mantém z0 
Estado final - repete o passo anterior 
 
2- 
 
3- a) A hipótese de Church refere-se a: tudo que pode ser calculado é computável através 
de uma MT. A importância a essa hipótese se dá pelo fato de que antes apenas existia a 
noção de que certas coisas podiam ser feitas, mas não se conseguia provar que certas 
coisas não podiam ser feitas, e durante a busca para formalizar se algo podia ou não ser 
calculável surgiu a tese. O problema dela não ser demonstrável se dá pelo fato que não 
existe uma formalidade do que pode ser efetivamente calculável, o que existe são 
evidencias de que conseguimos calcular qualquer problema através de uma MT. 
 
b) Devido a MT da classe das linguagens recursivamente enumeráveis ter dois 
comportamentos diferentes caso a palavra não seja aceita pela linguagem, onde no 
primeiro ela recusa a palavra e para, e no segundo, entra em loop infinito, enquanto na 
classe das linguagens recursivas a MT sempre para. 
 
4- a) Verdadeiro. Toda linguagem recursiva também é enumerável recursivamente. Para 
que L seja considerada uma linguagem recursiva ela precisa parar, visto que linguagens 
recursivamente enumeráveis podem parar e rejeitar ou entrar em loop quando se roda 
qualquer cadeia que não é da linguagem. Então dado que existem M1 e M2 MTs que 
aceitam L e ~L, e uma máquina não-determinística, para qualquer palavra de entrada, L 
para, sendo assim uma linguagem recursiva. 
 
b) Verdadeiro. Se imaginarmos que existe uma MT que aceita a linguagem L para 
qualquer entrada, logo também podemos imaginar uma MT contrária a nossa MT inicial, 
que aceitaria ~L também para qualquer entrada, sendo assim, o complemento de uma 
linguagem recursiva é uma linguagem recursiva. 
 
c) Falso. Como contraexemplo, se toda linguagem recursiva também é enumerável 
recursivamente, assim como descrito na letra a, logo a classe das linguagens recursivas 
está contida propriamente na classe das linguagens enumeráveis. 
 
d) Falso. Seguindo o princípio da tese de Church-Turing, se existe um problema 
efetivamente calculável, então existe uma MT (algoritmo) que o calcula.