Teoria da Computação: Exercícios e Máquinas Universais

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
 Teoria da Computação 
Lista de Exercícios: Codificação de Naturais, Norma e Post 
Profa Simone André da Costa Cavalheiro 
 
 
1. Considere a codificação de tuplas e programas monolíticos em IN vista em 
aula. Determine (V)erdadeiro ou (F)also, justificando. 
( ) Nem todo número natural codifica um programa monolítico. 
( ) Toda instrução de programa monolítico pode ser representada de forma 
única por um número natural. 
( ) O número 150 codifica duas quádruplas distintas. 
( ) O número natural 20.33.51.72 codifica uma instrução de programa 
monolítico. 
( ) O número natural 32.51.71 codifica uma instrução de programa monolítico. 
 
2. Qual a importância do estudo das Máquina Universais na Ciência da 
Computação? 
 
3. Mostre como os testes e instruções abaixo podem ser construídas como macros 
em Norma: 
a) A < 2 
b) A < B 
c) div(A, B) 
d) A := B – C 
e) A := A! 
f) A := AN 
 
4. Desenvolva os programas, em Norma, que realizam as operações abaixo nos 
inteiros: 
a) A := B + C 
b) A := B x C 
 
5. Descreva a diferença entre a classe de Linguagens Recursivas (ou Turing-
Decidíveis) e classe de Linguagens Enumeráveis Recursivamente (ou Turing-
Reconhecíveis). 
 
6. Dada uma palavra w sobre o alfabeto {a, b}, considera-se o inverso da palavra 
w, denotado por wi uma palavra de mesmo tamanho de w que tem todas as 
ocorrências de símbolos a substituídas por b e todas ocorrências de símbolos b 
substituídas por a. São dados alguns exemplos a seguir: 
w = aba wi = bab 
w = bbaaa wi = aabbb 
w = e wi = e 
 Defina uma máquina de Post ({a,b,$}, D, #) que aceite a linguagem 
{w$wi| w é uma palavra formada sobre o alfabeto {a, b}}.