Visualizing Why Nondeterministic Finite-State Automata Reject

In every Formal Languages and Automata Theory course, students are asked to design nondeterministic finite-state automata (NDFA). More often than not, students find this very challenging for several reasons. The first is that they are inexperienced with nondeterministic design. Second, in all likelihood, students lack the benefit of a programming language in which to implement their machines and receive immediate feedback. Such feedback is essential for students to debug a machine much like they debug a program (Landa and Martinez-Trevino, 2019; Marwan et al., 2020; Venables and Haywood, 2003). Third, most machine visualization tools are ill-equipped to help students understand why a word is rejected (or accepted) by a nondeterministic automaton. In addition, students need help understanding how a machine may perform multiple computations on the same input and how, unlike deterministic machines, there can be computations that do not consume all of the input word.

In the age of domain-specific languages (Bettini, 2016; Kleppe, 2008; Felleisen et al., 2018; Walter et al., 2009), it is an opportunity to provide students with a programming language that makes it relatively easy to program NDFAs. To this end, FSM (Functional State Machines) has been developed. FSM is a domain-specific language for the Automata Theory and Formal Languages classroom embedded in Racket. Its types include NDFA. Using FSM, students may test and debug their machines before attempting a proof or submitting a machine for grading. Furthermore, students can implement the algorithms they develop as part of their constructive proofs. An important feature of FSM is that programmers are not burdened with implementing nondeterminism. Instead, they may use nondeterminism just like they use any feature in their favorite programming language. Students design, implement, validate, and prove algorithms correct assuming nondeterminism is a built-in language feature.

One of the challenges with implementing such a language is providing support to understand and debug a nondeterministic machine addressing the problems outlined above. To understand the difficulties, it is important to recall when a nondeterministic machine accepts or rejects a given word. A nondeterministic machine accepts a given word if there is computation that takes the machine from its starting configuration to an accepting configuration. For an NDFA, an accepting configuration is one in which there is no more input to consume and the machine’s state is a final/accepting state. A word is rejected if there is no computation that takes the machine from its starting configuration to an accepting configuration. In other words, all possible computations must fail to end in an accepting configuration. If any possible computation ends in an accepting configuration then the machine accepts the word.

Providing support to demonstrate why a nondeterministic machine accepts a word, for example, is relatively easy. The programmer is provided with a trace of the configurations that take the machine from the starting state to a final state: C${}_{\textrm{0}}$ $\vdash$ C${}_{\textrm{1}}$ $\vdash$ $\ldots$C${}_{\textrm{n}}$. In such a sequence, C${}_{\textrm{i}}$ $\vdash$ C${}_{\textrm{j}}$ represents the application of a single rule, C${}_{\textrm{0}}$ is the starting configuration, and C${}_{\textrm{n}}$ is an accepting configuration. It is more challenging to provide support when a word is rejected, because for a nondeterministic machine we must show that all possible computations reject. The number of possible computations easily and quickly becomes unwieldy. Thus, providing a trace of all possible computations is of little use other than for the simplest nondeterministic machines. For this reason, until recently, FSM only informed the programmer that a word is rejected. This left students wondering why the machine they designed rejected. To address this shortcoming, FSM now provides the generation of computation graphs for NDFAs. A computation graph is a finite visualization to help explain nondeterministic behavior.

The article is organized as follows. Section 2 discusses and contrasts related work on visualization techniques for nondeterministic NDFAs. Section 3 presents a brief introduction to FSM. Section 4 presents and discusses computation graphs in FSM. Section 5 discusses how NDFA computation graphs are generated. Finally, Section 6 presents concluding remarks and directions for future work.

In most Formal Languages and Automata Theory textbooks, computations performed by a nondeterministic machine are visualized as a computation tree (e.g., (Gurari, 1989; Hopcroft et al., 2006; Lewis and Papadimitriou, 1997; Linz, 2011; Martin, 2003; Rich, 2019; Sipser, 2013)). In such trees, a node represents a machine configuration and an edge represents a transition. An NDFA configuration is a state and the unconsumed input. Nondeterministic decisions are represented by a node having multiple children reached reading the same element or having a child with the same unconsumed input (i.e., a transition without consuming input). Computation trees provide a trace of every possible configuration a machine may reach as all possible computations progress. A configuration, therefore, may appear multiple times in a computation tree. As a consequence, there are two potential hazards for students. The first is that the tree may become unwieldy large making it difficult to understand. The second is that students are easily tempted to look for differences between two identical configurations simply because they occur in different parts of the tree.

Classical automated tools to visualize why an NDFA rejects a word rely on exhaustively tracing all possible configurations a machine may reach when processing a given word. That is, they trace every path in a computation tree. JFLAP (Rodger, 2006; Rodger et al., 2006) and OpenFLAP (Mohammed, 2020), for example, provide a trace of every possible computation. Figure 1 displays an NDFA trace after 6 steps in JFLAP. Although a great deal of information is conveyed, there are two salient features that may present obstacles for learning. The first is that it is difficult to determine how a machine reached any of the configurations. The second is that the number of configurations that must be displayed can grow unwieldy and, therefore, become difficult to mentally organize. Another visualization tool is jFAST (White and Way, 2006). Similar to JFLAP, jFAST also has users manually render graph-based NDFA representations. Users can execute a machine by providing an input word. Unlike JFLAP, jFAST does not provide an option to see the series of transitions made during machine execution nor a trace of said transitions.

Modern approaches to automatically visualize NDFA computations present users with a computation graph. Like a computation tree, a computation graph has nodes that represent configurations. In a computation graph, however, a configuration is represented by a single node. Thus, different computations may have shared nodes. An undeniable benefit of the approach is that the size of the visualization is tamed. Gidayu, for example, uses computation graphs to visualize NDFA computations (Cogumbreiro and Blike, 2022). In a Gidayu NDFA computation graph, each node is rendered only using the configuration’s state. The unconsumed input is suppressed given that it may be reconstructed by tracing back to the starting configuration’s node. Thus, a machine state may appear repeatedly when it is part of different machine configurations. For instance, consider the sample NDFA displayed in Figure 2(a) (Cogumbreiro and Blike, 2022, p. 111) used to describe Gidayu. The computation graph generated for bb is displayed in Figure 2(b) (Cogumbreiro and Blike, 2022, p. 112). Observe that it has three nodes labeled q${}_{\texttt{3}}$. These nodes represent the configurations (from left to right): (q${}_{\texttt{3}}$ bb), (q${}_{\texttt{3}}$ b), and (q${}_{\texttt{3}}$ $\epsilon$). Gidayu’s computation graphs are useful for students trying to understand nondeterminism, because it is possible to determine how a configuration is reached and to determine if no accepting configuration is reached. A troublesome characteristic for some students is that a state may appear repeatedly in a computation graph. This is troublesome because students naturally associate a node with a state and not with a configuration. Another troublesome characteristic for some students is that a computation graph with nodes representing configurations does not derive its structure from the machine’s state transition diagram. For instance, the computation graph in Figure 2(b) is not contained in the state transition diagram displayed in Figure 2(a). For many students, therefore, it is not immediately obvious how a computation graph is related to the machine’s state transition diagram. Finally, there is no explicit indication that some computations do not consume the input word. For example, some students wonder what happens when the machine reaches the node representing (q${}_{\texttt{3}}$ bb) in Figure 2(b) (i.e., the leftmost occurrence of q${}_{\texttt{3}}$). To the readers of this article, it is clear that the machine halts and rejects on that computation. When students are first exposed to nondeterministic behavior, however, it is helpful to have a computation graph that explicitly indicates that computations may end in a node without consuming all the input.

Like Gidayu, FSM uses computation graphs, albeit different, to visualize NDFA computations. In contrast to the approaches outlined above, the FSM visualization reflects the structure of the machine’s state transition diagram. That is, FSM computation graphs are rendered based on the states traversed, not the configurations reached, by any potential computation. In this manner, the size of the visualization is bounded by the number of states and the size of the transition relation. Other than the addition of a dead state, to illustrate that some computations do not consume the entire input word, a computation graph is always a subgraph of the machine’s state diagram. Thus, students can easily see the connection between the machine’s state diagram and the visualization provided by FSM. Unlike the related work discussed above, the goal is not to trace every possible computation based on the configurations traversed. Instead, students are provided with a graphic that summarizes the behavior of all possible computations. To make it easy to determine if a word is accepted or rejected, state coloring is used to highlight all the states reached at the end of every computation when the input word is consumed. If none of the colored nodes reached is a final state then the machine rejects. If at least one of the colored nodes reached is a final state then the machine accepts. Finally, to highlight that some computations do not consume all the input, a dashed edge is added to a fresh dead state from a node in which a computation halts without completely consuming the input word. In the dead state, the rest of the input is consumed. Therefore, in an FSM computation graph the entire input word is consumed by every computation and students’ concerns about not consuming the entire input are eased. Nonetheless, as their understanding matures, students are able to understand, that dashed edges are not part of the machine and highlight states in which computations end without consuming the entire input word.

A primary goal for computation graphs is to visually demonstrate why a nondeterministic machine rejects a given word. They are equally useful in visually explaining why a nondeterministic machine accepts a given word. Given that, more often than not, students find computation graphs based on configurations confusing, a different representation is used in FSM. In an FSM computation graph, nodes represent states and edges represent transitions used by any possible computation that entirely consumes the given word. To guarantee that every possible computation entirely consumes the given word, if necessary, transitions to a fresh dead state are added. In an FSM computation graph, there are no repeated states. If a computation ends in a final state then we have visual proof that the word is accepted. If no computation ends in a final state then we have visual proof that the word is rejected.

There are two immediate concerns that arise with this approach. The first is that there must exist a way to distinguish states that are only traversed on all computations from states reached at the end of any computation. In an FSM computation graph, this is achieved by using color. States in which any computation ends are highlighted in crimson and all other nodes are black. Observe that a state highlighted in crimson may also be an intermediate state is some computations.

The second is how to represent a computation that does not entirely consume the given word. A nondeterministic machine, unlike a deterministic machine, may reach a non-accepting configuration in which no transition rules apply. By definition, the machine halts and rejects. This makes computation graphs difficult to read, because a state may be highlighted in crimson both if the input is or is not completely consumed. To eliminate this potential pitfall, when no transitions apply, a transition consuming the next word element to a fresh non-accepting dead state is added. In the dead state, the remaining input is consumed. In this manner, all computations end in a state in which all the input is consumed. A student may easily conclude that the input word is not in the machine’s language because it is completely consumed and rejected by all computations.

A nice characteristic of DFAs and NDFAs is that they decide a language. That is, they always accept or reject the given word. This means that a computation graph can always be constructed because every possible computation is guaranteed to end. This holds in FSM even when there are loops only involving $\epsilon$-transitions, because FSM’s implementation of nondeterminism does not explore the same configuration more than once.

This article presents a novel graphical approach to help students understand why nondeterministic finite-state automata reject a given word. The approach is integrated into FSM–a domain-specific language that allows programmers to easily build and execute such machines. Unlike previous approaches, that focus on tracing machine configurations, the work presented here builds on the transition diagram of a given machine. The nodes in an FSM computation graph represent states traversed by any computation and the edges represent the transitions used in any computation. Computation graphs are purposely built with a fresh dead state, if needed, so that all computations may consume all their input. States reached that satisfy this criteria, in any possible computation, are highlighted in crimson to indicate where at least one computation ends. The result is the generation of computation graphs that summarize what happens on all computations. They allow students to easily determine if any crimson states are final states. If none are, then they can see that the machine rejects because no computation ends in an accepting configuration. In addition, students easily associate a computation graph with a machine’s state transition diagram and can easily determine transitions used and states traversed during any computation. Finally, computations for accepted words only contain states and transitions traversed to reach an accepting configuration.

Future work includes the generation of computation graphs for pushdown automata and for Turing machines that decide and semidecide a language. Generation of such graphs requires care, because the length of a computation may be infinite. This means that in some cases it may only be possible to approximate a computation graph.