Equivalencia -teoria da computacao

UNIVERSIDADE ESTADUAL DE GOIÁS BACHAREL EM SISTEMAS DE INFORMAÇÃO VERIFICAÇÃO DA EQUIVALÊNCIA FORTE DE PROGRAMAS

1. Programas iterativos e monolíticos podem ser transformados em programas recursivos fortemente equivalentes, o problema desta afirmação é desenvolver um método geral (algoritmo) para definir uma sequência finita de passos aplicável um par de programas recursivos. Descreva a solução deste algoritmo. “Até o atual momento não é conhecido se este problema é solucionável, ou seja, não há um algoritmo para fazer esta verificação.” 2. Como a Máquina de Traços define a equivalência forte de programas? “A Máquina de Traços cria um histórico das ocorrências das operações, denominado traço. Este traço é uma palavra sobre um alfabeto de identificadores de operações. Se dois programas são equivalentes em uma máquina de traços eles são equivalentes fortemente.” 3. Dentro de um fluxograma o que são os nós? “Dentro de um fluxograma os nós são uma denominação genérica para os componentes elementares: partida, parada e operações.” 4. O que é um Programa Monolítico com Instruções Rotuladas Compostas? “Um Programa Monolítico com Instruções Rotuladas Compostas é um par ordenado com o conjunto de Instruções Rotuladas e o Rótulo Inicial do programa.” 5. É correto afirmar que podem existir duas instruções com um mesmo rótulo? Justifique e em caso afirmativo demonstre uma condição.

“Não é correto afirmar. Não existem instruções iguais com um mesmo rótulo, mesmo que existam instruções iguais seus rótulos não podem ser iguais já que estão em locais distintos no fluxo e também levam a fluxos distintos no fluxograma.” 6. Quais as diferenças entre Instruções Rotuladas e Instruções Rotuladas Compostas? “As Instruções Rotuladas possuem duas formas: teste e operação. Enquanto as Rotuladas Compostas possuem uma só forma que combinada as duas formas da Rotulada em uma só.” 7. Como verificar a equivalência forte de programas com Instruções Rotuladas Compostas? “Para verificar a