ListaExercicios_4

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO DE CIÊNCIAS EXATAS, NATURAIS E DA SAÚDE – CCENS/
UFES
Departamento de Computação
Lista de exercícios 4
Disciplina: Teoria da Computação
Professora: Juliana Pinheiro Campos Pirovani
Assunto: Descrições de MT, Funções recursivas, Decidibilidade e Redutibilidade.
1) Dê descrições a nível de implementação de MT que decidem as linguagens abaixo sobre 
o alfabeto {0,1}
a) {w| w possui o mesmo número de 0s e 1s}
b) {w| w contém duas vezes mais 0s que 1s}
c) {w| w não contém duas vezes mais 0s que 1s}
2) Dê a descrição de alto nível para as seguintes MT:
a) MT que realize a operação fatorial (fat(A)). 
b) MT que realize a potência (pot(A,B)).
3) Compare e diferencie claramente as funções fzero e a função constante constZero.
4) Desenvolva funções recursivas parciais (ou de Kleene) sobre N para as seguintes 
operações:
a) Quadrado(n2)
b) Fatorial(n!)
c) E_um(n) : retorna 1 se n = 1 e 0, caso contrário.
d) Igual(m, n): retorna 1 se m e n são iguais; e 0, caso contrário. OBS: Use as 
funções ezero,mult e maior_ou_igual vistas em sala.
5) Responda V ou F:
a) ( ) Se D é um problema de decisão decidível e D é redutível a X, pode-se dizer 
que X também é decidível.
b) ( ) Um problema não-solucionável é aquele que não pode ser computável.
c) ( ) Um problema é computável quando ele é parcialmente solucionável.
d) ( ) Um problema é dito parcialmente solucionável se existe um programa em 
uma máquina de Turing que solucione o problema tal que para quando a resposta 
esperada é negativa.
e) ( ) A união das classes dos problemas solucionáveis, dos problemas 
computáveis, dos problemas parcialmente solucionáveis com a dos problemas não
computáveis é o universo de todos os problemas.
f) ( ) A classe dos problemas solucionáveis é equivalente à classe das linguagens 
recursivas.
6) Responda a cada um dos itens abaixo para o AFD M e justifique suas respostas: 
Lembre-se que:
AAFD = {<B, w> | B é um AFD que aceita a cadeia w}
AEXR = {<R, w> | R é uma ER que gera a cadeia w}
VAFD = {<A> | A é um AFD e L(A) = ᴓ}
EQAFD= {<A, B> | A e B são AFD’s e L(A) = L(B)}.
a) <M, 0100> AAFD? 
b) <M, 011> AAFD? 
c) <M> AAFD? 
d) <M, 0100> AEXR? 
e) <M> VAFD? 
f) <M, M> EQAFD? 
7) O conjunto dos números primos é recursivamente enumerável? É recursivo? Justifique. 
8) Considere o problema de se determinar se um AFD e uma expressão regular são 
equivalentes. Expresse esse problema como uma linguagem e mostre que ele é decidível.
9) Seja TODASAFD = {<A> | A é um AFD e L(A) = Σ*}. Mostre que TODAS}. Mostre que TODASAFD é 
decidível.
10) Seja A = {<M> | M é um AFD que não aceita nenhuma cadeia contendo um número 
ímpar de 1’s}. Mostre que A é decidível.
11) Mostre que o problema de se testar vacuidade para a linguagem de uma GLC é decidível. 
Ou seja, mostre que VGLC = {<G> | G é uma GLC e L(G) = ᴓ } é decidível.
12) Mostre que não existe uma função em C que receba uma outra função por parâmetro e 
retorne true se a função pára e false se a função não pára. Use redução.
13) Prove que REGULARMT = {<M> | M é uma MT e L(M) é uma linguagem regular} é 
indecidível. 
14) Explique porque A é decidível sabendo que:
a) A é Turing-reconhecível
b) A é redutível a A
c) Se A é redutível a B e B é Turing-reconhecível, então A é Turing-reconhecível.