Exercícios de Teoria da Computação

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
2
o
 semestre de 2011 
 
 
GCC108 – Teoria da Computação 
Professor Responsável: Leonardo Andrade Ribeiro 
 
 
Avaliação: Exercícios 2 
Data: 20.10.2011 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
 
1) Construa uma Máquina de Turing Numérica (MTN) que compute a função 
 ( ) ⌊ ⌋, onde ⌊ ⌋ é o menor inteiro menor ou igual a ? 
 
 
 
Comentário: Assumindo que a entrada não é vazia, estados q1 e q2 transformam um 
entrada do tipo 111111 (5, em notação unária) em 1x1x1x. A eliminação dos 
marcadores x é realizada nos estados q5, q6, q7. 
2) Considere o seguinte repertório de macros : 
MDk – move a cabeça le k números naturais à direita. A macro termina com a 
cabeça le posicionada sobre o símbolo branco imediatamente posterior ao kth 
número natural à direita da posição atual. 
MEk – move a cabeça le k números naturais à esquerda. A macro termina com a 
cabeça le posicionada sobre o símbolo branco imediatamente anterior ao kth 
número natural à esquerda da posição atual. 
ED – Posiciona a cabeça le sobre símbolo branco imediatamente anterior ao 
primeiro natural à direita da posição atual. 
EE – Posiciona a cabeça le sobre símbolo branco imediatamente anterior ao 
primeiro natural à esquerda da posição atual. 
Ak – Apaga k números naturas à direita da posição atual cabeça le. A macro 
termina com a cabeça le na posição original. 
CPk – Copia k números naturais para as posições iniciando-se imediatamente à 
direita do último número a ser copiado e termina com a cabeça le na posição 
original. 
CPk,i – Copia k números naturais para as posições iniciando-se i números naturais à 
direita do último número a ser copiado e termina com a cabeça le na posição 
original. 
T – Move o primeiro número natural à direita da cabeça le para a posição 
imediatamente à direita da mesma; termina com a cabeça le na posição original. 
ADD – Soma os dois números naturais mais à direita da cabeça le. A macro 
termina com a cabeça le na posição original e o resultado da soma escrito na 
posição imediatamente à direita da mesma. 
 
Usando R, construa máquinas para computar: 
a) ( ) 
 
Comentário: Notem a pequena correção na descrição de ADD 
 
b) ( ) 
 
 
 
 
3) Considere a macro MULT acima que computa a multiplicação de dois números 
naturais. Baseando-se em MULT, mas sem usar a mesma, construa uma macro que 
compute ( ) . 
 
 
4) Considere uma função definida pela seguinte composição funcional: 
 ( 
( ) ( 
( ) 
( ))) 
Calcule o valor de ( ) apresentando as etapas intermediárias da calculação. 
 
 
Comentário: Para saber como proceder, vejam os slides sobre Funções Recursivas, 
versão 0.91, nr. 10. 
 
 
 
 
 
 
 
 
 
 
 
 
 
5) Seja ( ) e ( ) e seja ( ) a função definida por e 
via recursão primitiva. Calcule o valor de ( ) apresentando as etapas 
intermediárias da calculação. 
 
 
Comentário: Para saber como proceder, vejam os slides sobre Funções Recursivas, 
versão 0.91, nr. 48, 50 e 53. 
 
 
 
 
 
 
6) Seja ( ) uma função recursiva primitiva. Mostre que a função também é 
recusiva primitiva: 
 ( ) ( ) 
 
 
Resposta: ( 
( ) 
( ) 
( )) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7) Usando apenas as funções básicas, composição e recursão primitiva (para recursão 
primitiva, apresente as funções e ), mostre que ( ) é recursiva 
primitiva. 
 ( ) ( ) 
 ( ) ( ( )) ( ) 
( )
 
 
Tabela 1 
Descrição Função Definição 
adição ( ) 
x+y 
 ( ) 
 ( ) ( ) 
multiplicação mult( ) 
x*y 
mult( ) 
 ( ) ( ) 
predecessor pred(y) pred(0) 
pred(y+1) = y 
sub sub(x,y) sub(x,0)=0 
sub(x,y+1)=pred(sub(x,y)) 
sinal sg(y) (0) = 0 
 (y+1) = 1 
sinal comp. cosg(y) (0) = 1 
 (y+1) = 0 
par par(y) 
 
par(0) = 1 
par(y+1) = cosg(par(y)) 
less than lt(x,y) sg(sub(y,x)) 
greater than gt(x,y) sg(sub(x,y)) 
equal to eq(x,y) ( ( ) ( )) 
 
 
 
 
 
 
8) Seja e funções recursivas primitivas. Mostre que função abaixo é recursiva 
primitiva (Voce pode usar qualquer função da Tabela1 e também qualquer 
operador limitado): 
 ( ) {
 ( ) ( ) 
 
 
 
 
Resposta: Temos que ( ) retorna 1 se é monotonicamente decrescente no 
intervalo [ ]. Nos slides sobre Funções Recursivas, versão 0.91, nr. 84-85, tem 
uma possível resposta (existe mais uma resposta possível) para a variante onde ( ) 
retorna 1 se é monotonicamente crescente. 
 
 
 
 
 
 
 
 
 
9) Descreva a seguinte função primitiva recursiva (pode usar uma descrição informal, 
desde que precisa): 
 ( ) 
 
 
[ ( ) ( 
 
 
[ ( )])] 
 
Resposta: ( ) retorna o segundo menor valor no intervalo [ ] para o qual é 
verdadeiro. 
 
Comentário: De acordo com a definição, o operador limitado irá retornar o menor 
valor para z no intervalo [ ] que faça ( ) ( 
 
[ ( )]) . 
Informalmente, é realizada uma busca na qual a expressão é avalida sucessivamente 
com , ..., etc, até que seja encontrado para a qual o 
resultado da expressão é 1--- neste caso é retornado como resultado do operador . 
 
Considere o predicado (qual predicado é exatamente não é importante) e suponha 
que é o primeiro valor para no qual ( ) . Neste caso teremos: 
 ( ) ( 
 
 
[ ( )]) 
 
 ( 
 
 
[ ( )]) 
O operador interno é então avaliado. Temo que o valor encontrado também será 3. 
Dessa maneira: 
 ( ) 
 
 
 
Portanto, o valor da expressão é 0 e a busca com o operador operador externo 
prossegue com na próxima interação. Neste ponto, a expressão pode ser 
substituída por: 
 ( ) ( ) 
 
Ou seja, a busca será pelo menor valor para no intervalo [ ] que faça . 
Como é o menor valor para o qual , a busca retornará o segundo menor valor 
para o qual é verdadeiro ( ). 
 
Neste contexto, o que a função abaixo retornaria? 
 
 ( ) 
 
 
[ ( ) ( 
 
 
[ ( ) ( 
 
 
[ ( )])])]