Máquinas de Turing em OCAML-FLAT/OFLAT

Abstract

Para ajudar no ensino dos conceitos de Teoria de Linguagens Formais e Autómatos (FLAT - Formal Languages and Automata Theory) são desenvolvidas diversas ferramentas pedagógicas. É esta a motivação que justificou, em 2018, o início da elaboração da biblioteca OCaml-FLAT e da aplicação web OFLAT. Ambas as ferramentas estão escritas em OCaml, tentando usar deliberadamente um estilo funcional declarativo, que em alguns casos se consegue aproximar dos formalismos teóricos ensinados aos alunos. Esta dissertação visou estender as referidas ferramentas com a adição de suporte para máquinas de Turing. Foram desenvolvidas as funcionalidades normais destes modelos, tanto na biblioteca, ao nível lógico, como na aplicação gráfica, através duma interface gráfica ambiciosa com preocupações pedagógicas. Alguns exemplos de funcionalidades desenvolvidas para as máquinas de Turing são: criação; edição; simulação da execução; aceitação e geração de palavras; determinação de propriedades particulares; conversões de/para outros tipos de modelos. Também foi introduzido suporte para máquinas de Turing linearmente limitadas. Destaque para a animação gráfica da execução de máquinas de Turing possivelmente não deterministas, e para a operação de conversão direta de autómatos de pilha para máquinas de Turing com fita simples (não foram encontradas soluções concretas na literatura). Neste documento apresenta-se e discute-se o resultado deste trabalho.