The Implementation of FSM Computation Graphs
Marco T. Morazán, Oliwia Kempinski, Andrés M. Garced · 2024
In their first Formal Languages and Automata Theory course, students find nondeterminism challenging.Most students struggle to understand the operational semantics of nondeterministic machines.Often, this includes understanding why a nondeterministic machine accepts or rejects a word, why there can be multiple computations on the same input, and, unlike a deterministic machine, why all the input is not consumed.This article presents a visualization tool, and its implementation, developed to help students understand nondeterministic behavior.The tool is integrated into FSM-a functional domain-specific language for the Automata Theory classroom.The strategy is based on the automatic generation of computation graphs.Unlike previous visualization tools, the computation graphs generated reflect the structure of the given machine's transition diagram and not the structure of the computation tree.Data obtained, as part of a formative study, from students using the described computation graphs suggests that they are well-received and useful.