Document details

This dissertation presents the design and implementation of finite state transducers (FSTs) within the OCamlFLAT/OFLAT application, a web-based educational tool for exploring concepts in computation theory developed at FCT NOVA. Finite state transduc- ers extend finite automata by associating output symbols with transitions, enabling the modeling of transformations from input to output strings. The current system consists of two separate components: Firstly, we have the OCamlFLAT library, a library with all the data structures and logic regarding the theoretical concepts of its supported models. And secondly, the OFLAT web application, which is built on top of the OCamlFLAT library, provides a pedagogical interactive graphic interface for users to explore the models supported by the library. Both tools were written in OCaml, deliberately aiming to use a functional declarative style, which in some cases manages to closely resemble the theoretical formalisms taught to students. It is a system that is in constant evolution, with new features being added to both the library and the web application. The work to be developed in this thesis involves the extension of these tools with new operations over transducers, such as translation, acceptance, generation, classification and conversion. Additionally, the new concepts must be integrated in OFLAT’s ecosystem, which includes model composition, and pedagogical exercises for students to practice and test their knowledge. The resulting system will allow users to build, modify, and analyze FSTs visually, supporting better comprehension of theoretical principles through experimentation.

Esta dissertação apresenta o projeto e a implementação de transdutores finitos (FSTs) na aplicação OCamlFLAT/OFLAT, uma ferramenta educacional baseada na web para a exploração de conceitos de teoria da computação, desenvolvida na FCT NOVA. Os trans- dutores finitos estendem os autómatos finitos ao associar símbolos de saída às transições, permitindo a modelação de transformações entre cadeias de entrada e de saída. O sistema atual é composto por dois componentes distintos: a biblioteca OCamlFLAT, que contém todas as estruturas de dados e lógica associadas aos conceitos teóricos dos modelos suportados; e a aplicação web OFLAT, construída sobre a biblioteca OCamlFLAT, que fornece uma interface gráfica interativa com fins pedagógicos para que os utiliza- dores possam explorar os modelos suportados pela biblioteca. Ambas as ferramentas foram desenvolvidas em OCaml, procurando adotar deliberadamente um estilo funcional declarativo, que em alguns casos se aproxima dos formalismos teóricos ensinados aos alunos. Trata-se de um sistema em constante evolução, com novas funcionalidades a serem acrescentadas continuamente tanto à biblioteca como à aplicação web. O trabalho a desenvolver nesta dissertação envolve a extensão destas ferramentas com novas operações sobre transdutores, tais como tradução, aceitação, geração, classificação e conversão. Adicionalmente, os novos conceitos devem ser integrados no ecossistema do OFLAT, o que inclui a composição de modelos e a criação de exercícios pedagógicos para os alunos praticarem e testarem os seus conhecimentos. O sistema resultante permitirá aos utilizadores construir, modificar e analisar transdutores finitos de forma visual, promovendo uma melhor compreensão dos princípios teóricos através da experimentação.