Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
2009.2
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
Compartilhar
Prévia do material em texto
Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Informática Teórica
(IF689)
2º Semestre de 2009
5ª Mini-Prova
23 de Outubro de 2009
1. (0.3) Seja B uma MT onde L(𝐵 ) é Turing-reconhecível e co-Turing-
reconhecível e A outra MT onde existe uma função computável que mapeia os
elementos de A em B. Prove que A é decidível.
2. Seja M = ({q0, q1, qa, qr}, {0, 1}, {0, 1, ⊔}, δ, q0, qa, qr) com δ definida da
seguinte forma:
δ (q0, 0) = (q0, 0, D) δ (q0, 1) = (q0, 1, D) δ (q0, ⊔) = (q1, ⊔, E)
δ (q1, 0) = (q1, 0, E) δ (q1, 1) = (q2, 1, E)
δ (q2, 0) = (qa, 0, E) δ (q2, 1) = (q2, 1, E)
Mostre o conjunto de peças (0.3) e o emparelhamento (0.4) do PCPM para a cadeia
1001.
Continue navegando
Perguntas relacionadas
Compartilhar