Using Computation Graphs to Explain Nondeterminism to Students

Students find their first course in Formal Languages and Automata Theory challenging. Most students struggle to understand nondeterministic computation models like nondeterministic finite-state machines, pushdown automata, and Turing machines. 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 computation not consuming all of its input. This article presents 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. 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. Empirical data collected from students at two universities suggests that the visualizations are well-received and useful.