Prévia do material em texto
UNIVERSIDADE FEDERAL DE PELOTAS Teoria da Computação Lista de Exercícios 4 Profa Simone André da Costa 1. Converta os seguintes programas iterativos em programas monolíticos fortemente equivalentes. Programa Iterativo P1 (Se T1 então F senão enquanto T2 faça (G; F; Até T3 faça (F))) Programa Iterativo P2 Até T1 faça (F; G); Enquanto T2 faça (F; (Se T3 então I senão G)) Programa Iterativo P3 F; G; (Se T então F; G senão Até T faça (G; Enquanto T faça (F))) Programa Iterativo P4 Enquanto T faça (F); (Se T então Enquanto T faça (G) senão I); H 2. Converta os programas monolíticos obtidos na questão 1 em programas recursivos fortemente equivalentes. 3. O que significa dizer que dois programas, P e Q, são fortemente equivalentes? 4. A respeito de equivalência forte, determine verdadeiro ou falso e justifique: a. ( ) Se os programas P e Q são fortemente equivalentes, então eles possuem as mesmas instruções. b. ( ) Dois programas que são fortemente equivalentes devem computar a mesma função em todas as máquinas. c. ( ) Dois programas P e Q, fortemente equivalentes, podem computar uma mesma função f em uma máquina M1 e uma mesma função g, diferente de f, em uma máquina M2. d. ( ) Para todo programa iterativo, existe um programa recursivo fortemente equivalente. 5. Determine verdadeiro ou falso e justifique: a. ( ) Para qualquer programa monolítico P, existe um programa iterativo Q que computa a mesma função. b. ( ) Se dois programas são fortemente equivalentes, então a sequência de operações e testes por eles executadas é a mesma. c. ( ) A análise da equivalência forte permite identificar programas com estruturas diferentes mas com computações isomórficas. d. ( ) Para todo programa monolítico P, existe um programa iterativo Q tal que para qualquer máquina M, a função computada por P em M é a mesma função computada por Q em M. 6. Descreva o procedimento para provar que nem todo programa recursivo pode ser traduzido para um monolítico fortemente equivalente (não precisa fazer a prova, mas descrever o que é necessário para concluí-la).