I wanted honors credit for CS520 for the fall semester of the 1999-2000 year, so I wrote a non-deterministic finite automaton (NFA) simulator as a semester project. I designed the simulator as a Java applet so that everyone could play with it in their web browsers, and hopefully find it to be a useful learning tool for the theory of computing. If you'd like to make a comment about the applet, or report a bug, please send me e-mail at rw.

What is does

The simulator lets you construct an NFA, then step through its computation process on words of your choice.

How to use it

The controls for the applet are:

• To create a state, hold shift and left-click an empty area.
• To select a state, simply click it.
• To move a state, click and drag it. [Note: this functionality does not work with Netscape 4's built-in JVM]
• To create a transition from one state to another, first select the source state. Then, right-click the destination state (it should then be selected in red). Now type the characters of the transitions you would like to have from the source state to the destination state. To make an EPSILON transition, press the SPACE BAR.
• To remove a transition, follow the same steps as in creating a transition, but type BACKSPACE as the transition character.
• To toggle an accept state, hold shift and click the state.
• To remove a state, hold shift and right-click the state. Note that you cannot delete the start state (the state with the black triangle pointing to it), because the computation begins at this state.
• To change a state's name simply select the state, then type its new name. Press backspace to delete characters from the end of the name.
• To begin a new computation, type a word into the Word text field, then press enter.
• To step through a computation, click the Step button.
• To change the step increment, type a new value into the Step size text field, then press enter. Clicking the Step button will then cause the computation to proceed by that many steps at a time.
• To restart the computation from the beginning of the word, click the Restart button.

The applet

Your browser does not support Java applets. Too bad.

The source

The applet's code is contained in six source files:

• FiniteAutomaton.java – an extension of the FiniteStateMachine model, the FiniteAutomaton class is the main class for constructing an NFA. It allows you to observe the NFA's computations step-by-step.
• FiniteStateMachine.java – an abstract superclass designed to flexibly support models such as finite automata, pushdown automata and Turing Machines, the FiniteStateMachine class contains all the necessary logic for rendering a finite state machine's state diagram to the screen as a Java GUI Component.
• FSMApplet.java – the FSMApplet class provides a user interface for manipulating the computation status of NFAs, PDAs and TMs. For now, only NFAs are supported.
• State.java – this class represents a single state in a finite state machine.
• TransitionFunction.java – the transition function class, it maintains the collection of transitions from a given tuple to another tuple (e.g., (state, letter) -> (state)).
• TransitionTuple.java – this class represents a tuple, and is used by the TransitionFunction class to facilitate quick storage and retrieval of individual transitions using a hashtable.