Linguagens Formais

Linguagens Formais

1. Programa

   • a formalização dos conceitos de programa e de máquina não é baseada em qualquer linguagem ou computador real.
   • Conjunto de operações e testes compostos de acordo com uma estrutura de controle.
     • monolítico
       • é estruturado usando desvios condicionais e incondicionais
         • Por exemplo, uso do if e do else, necessitando de um desvio entre T ou F
       • é um par ordenado P = (I,r)
       • Problemas
         • Dificuldade na manutenção e entendimento;
         • Liberdade dos desvios incondicionais: “quebra de lógica”
         • Solução
           • estruturas de controle de ciclos ou repetições
     • iterativo
       • estruturas de controle de ciclos ou repetições
         • Por exemplo, while e for
     • recursivo
       • Admite a definição de sub-rotinas recursivas
         • estruturação hierárquica de programas, possibilitando níveis diferenciados de abstração.
           • Por exemplo, as funções
     • duas ou mais operações ou testes podem ser compostos
       • Composição sequencial
         • operação ou teste subsequente somente pode ser realizada após o encerramento da execução da operação ou teste anterior
       • Composição não determinística ou escolha
         • operação ou teste a ser executado é uma escolha entre diversas alternativas de operações ou testes compostos.
       • Composição concorrente
         • a ordem de execução é irrelevante

2. Máquina

   • Interpreta os programas de acordo com os dados fornecidos
     • só consegue se tiver uma interpretação para cara operação ou teste

3. Computação

   • Histórico do funcionamento da máquina para o programa, considerando o valor incial
   • Função computada
     • função induzida a partir da máquina e do programa dados
       • caracterizada por um valor de entrada e saída
         • a saída espera-se ser gerada em tempo finito
     • programas fortemente equivalentes
       • coincidem para qualquer máquina
     • programas equivalentes
       • coincidem para uma dada máquina
     • máquinas equivalentes
       • máquinas podem simular umas às outras

Imágenes y archivos del mapa