2011.1
1 pág.

2011.1


Disciplina<strong>infor</strong>1 materiais
Pré-visualização1 página
Universidade Federal de Pernambuco (UFPE) 
Centro de Informática (CIn) 
Informática Teórica 
(IF689) 
5ª Mini-Prova 
01 de Junho de 2011 
 
1. (0.5) Prove que a linguagem \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd = {<M> | M é uma máquina 
de Turing e L(M) é uma linguagem regular} é uma linguagem indecidível. 
Obs.: Você pode utilizar qualquer outro problema indecidível em sua 
prova. 
 
2 (0.5) De acordo com M e w a seguir, responda o que se pede. 
w = 010. 
M = {{	
, 	\ufffd, 	
, 	\ufffd}, {0,1}, {0, 1, \u2294}, \u3b4, 	
, 	
, 	\ufffd}, com \u3b4 definida da 
seguinte maneira: 
\u3b4(	
, 0) = (	
, 0, D); \u3b4(	\ufffd, 0) = (	\ufffd, 0, D); 
\u3b4(	
, 1) = (	\ufffd, 1, D); \u3b4(	\ufffd, 1) = (	
, 0, E); 
\u3b4(	
, \u2294) = (	
, \u2294, D); \u3b4(	\ufffd, \u2294) = (	\ufffd, 1, E). 
(a) (0.25) Mostre o conjunto de peças utilizado no emparelhamento 
correspondente à computação de M sobre w. 
(b) (0.25) Mostre o emparelhamento correspondente à computação de M 
sobre w.