Autómatos de Pilha nas ferramentas OCaml-FLAT/OFLAT

Abstract

Os conceitos de Teoria de Linguagens Formais e Autómatos (FLAT - Formal Languages and Automata Theory) são abstratos, formais e matemáticos. Devido a isso, a aprendizagem desses tende a ser complicada para alguns alunos. Para apoiar o ensino dos conceitos FLAT, historicamente têm sido criadas múltiplas ferramentas informáticas. Duas ferramentas que foram desenvolvidas na FCT/UNL nos últimos anos são a biblioteca OCaml-FLAT e a aplicação Web OFLAT. Ambas as ferramentas foram escritas em OCaml, tentando usar deliberadamente um estilo funcional declarativo, que em alguns casos se consegue aproximar dos formalismos teóricos que são ensinados aos alunos. As duas ferramentas estão escritas em OCaml e encontram-se em evolução e crescimento. Esta dissertação visou adicionar autómatos de pilha ao conjunto de modelos suporta- dos pelas ferramentas. Foram desenvolvidas as funcionalidades normais esperadas neste domínio como por exemplo: criar e editar autómatos, reconhecer palavras, gerar palavras, determinar propriedades, efetuar conversões de/para outros tipos de modelo. Ao nível da biblioteca foi desafiante lidar com questões de não determinismo, estruturas cíclicas e casos de potencial não terminação. Na aplicação gráfica existiu a ambição de desenvolver uma interface gráfica criativa, intuitiva e pedagógica, oferecendo uma rica panóplia de operações. Destaque para o grande investimento colocado na animação da operação de reconhecimento de palavras para autómatos de pilha possivelmente não deterministas. Neste documento apresenta-se e discute-se o resultado deste trabalho.

The concepts of Theory of Formal Languages and Automata (FLAT - Formal Languages and Automata Theory) are abstract, formal and mathematical. Because of this, their learning tends to be complicated for some students. To support the teaching of FLAT concepts, historically, multiple computer tools have been created. Two tools that were developed at FCT/UNL are the OCaml-FLAT library and the OFLAT Web application. Both tools were written in OCaml, deliberately trying to use a declarative functional style, which in some cases managed to approach the theoretical formalisms taught to the students. Both tools are written in OCaml and are evolving and growing. This dissertation aimed to add pushdown automata to the set of models supported by the tools. The normal functionalities expected in this domain were developed, such as: creating and editing automata, recognizing words, generating words, determining properties, converting to/from other types of models. At the library level it was challenging to deal with issues of non-determinism, cyclical structures and cases of potential non-termination. In the graphical application, there was the ambition to develop a creative, intuitive and pedagogical graphical interface, offering a rich range of operations. A highlight is the large investment made in animating the word recognition operation for possibly non-deterministic pushdown automata. This document presents and discusses the result of this work.