  Students find their first course in Formal Languages and Automata Theory
challenging. In addition to the development of formal arguments, most students
struggle to understand nondeterministic computation models. In part, the
struggle stems from the course exposing them for the first time to
nondeterminism. Often, students find it difficult to understand why a
nondeterministic machine accepts or rejects a word. Furthermore, they may feel
uncomfortable with there being multiple computations on the same input and with
a machine not consuming all of its input. This article describes a
visualization tool developed to help students understand nondeterministic
behavior. The tool is integrated into, FSM, a domain-specific language for the
Automata Theory classroom. The strategy is based on the automatic generation of
computation graphs given a machine and an input word. Unlike previous
visualization tools, the computation graphs generated reflect the structure of
the given machine's transition relation and not the structure of the
computation tree.

Programming Languages