Resumo: Em 1956, Kleene apresentou, juntamente com o conceito de
expressão regular, um dos mais simples modelos de computação: o de
autómato finito determinístico. Ao mesmo tempo, Kleene provou um teorema
enunciando que são coincidentes a classe de linguagens que é possível
especificar usando expressões regulares e a classe de linguagens aceite
por autómatos determinísticos.
Um dos resultados mais significativos do nosso trabalho de
investigação consiste na proposta de uma extensão do trabalho inicial de
Kleene para uma classe alargada de modelos de computação. Assim,
apresentamos uma forma homogénea de derivar linguagens de expressões
regulares para modelos de computação como os autómatos de Mealy, usados
no contexto de desenvolvimento de circuitos digitais; consideramos
também modelos que incluem comportamentos aleatórios (autómatos
probabilisticos), que se tornaram mais relevantes nos últimos anos
visando a análise quantitativa de sistemas com o objectivo de se poder
prever a probabilidade de um sistema falhar.
O valor do nosso contributo pode ser avaliado segundo dois prismas
diferentes: por um lado, permite a derivação de linguagens já existentes
na literatura; por outro, possibilita a derivação de novas linguagens
(e axiomatizações) para modelos de computação para os quais não existia
um teorema de Kleene ou axiomatização, apesar de terem sido já
largamente estudados ao longo dos anos. |