This program was developed for my third year undergraduate project (1995-6), entitled "An Interactive System for the Exploration of Finite State Machines."

Updates:

• Apr 2002: Added a dialog box for the conversion from non-deterministic operation, with a cancel button, as the conversion can take a very long time for large machines. It won't run with JDK 1.0.2 anymore (is that a problem?) but it should work with 1.1.x and all later versions.
• Nov 1999: Updated to work with JDK 1.2.2

Note: All code available from this page is copyright the University of Warwick, England.

The study of theoretical computational machines has always been based around static representations, usually on paper. However, one of the fundamental characteristics of these machines is that they are dynamic. As the complexity of machines being studied increases, it becomes increasingly difficult to represent their behaviour statically, and therefore correspondingly harder to visualize mentally.

This project attempts to rectify this situation through the development of an interactive graphical system which supports the construction of the class of computational machines known as finite state automata. Animation is then used to dynamically illustrate their behaviour on given inputs.

Furthermore, powerful manipulation facilities are developed to support the study and exploration of automata, including the conversion between equivalent classes of machine, and the automatic generation of layouts. Finally, input and output capabilities are provided to enable the continued development and reuse of constructed machines.

The program was implemented in the Java Programming Language, and is available here. The applet version should appear below if you are using a Java-enabled browser, with instructions below that.

All of the required class files can be downloaded (93k), and the program run as a standalone application, with the command:

java Machine.Main

The full source code is available, in tar.gz format (30k) and in zip format (42k) HTML documentation can be generated from comments in the source code with the command:

javadoc Machine

• Click in the main window to create new states, when in Add mode.
• To connect states, select Connect mode, then click on the state the connection is to originate from, so that it changes colour to green. Then click on the destination state, which should also become green. Then press a key for that transition, to create the connection. Valid characters for transitions are upper and lower case letters, and digits. Pressing any other key will cancel the connection operation.
• A valid machine must have a start state which can be designated when in Start mode.
• Toggle mode changes the acceptance status of states. All states are initially non-accepting.
• States can be repositioned by dragging them with the mouse when in Move mode.
• Delete mode can be used to remove states or connections. Click on the transition character(s) to remove a connection.
• The current mode can be changed by selecting from the toolbar, or by pressing the first letter of the mode name, when in the main window.

• The green panner widget can be used to scroll around the virtual workspace in which the machine may be contructed.
• The zoom slider can be used to vary the current scaling of the on-screen representation of the machine, from 50% to 200% of the default scaling.
• The "Start New" button will delete the entire machine, so that a new one can be constructed.

• To simulate a machine, enter an input string (in the box next to the Simulation button), select the required simulation speed, and click on the Simulation button. The input string is processed one character at a time, and the currently active state (or states, if the machine is non-deterministic) will change colour to green.

• The "Deterministic?" button will determine whether the current machine is deterministic - there is never more than one transition for a particular character originating from a state.
• The "Auto Layout" button will discard the machine's positional information and attempt to postion the states in such a way as to optimise the layout according to some criteria. However the method in full has complexity O(n!), where n is the number of states. So, only a couple of entries from the search space are chosen, at random. Thus the generated layout will generally be suboptimal. Clicking on the button again will repeat the process, which will probably give a different layout.
• The "Remove Inacc" button will remove any inaccessible states from the current machine.
• The "Minimize" button will remove inaccessible states, complete the machine (add any missing transitions, all going to a non-accepting state), find all indistinguishable states, and merge them together, to form a minimal machine. This is only applicable to deterministic machines.
• The "NonDet -> Det" button will convert the current non-deterministic machine to a deterministic machine. The states of the deterministic machine are the elements of the power set of the states of the non-deterministic machine. This routine has complexity O(2^n), where n is the number of states, so will be very slow for large machines.
• The last two operations call the layout routine to position the generated machines.

When running as an application, the following capabilities are available, from the "File" menu.

• "Save machine" and "Save machine as" write a full description of the current machine to a file.
• "Load machine" reads a previously saved machine description, and reconstructs the machine, wiping the current machine.
• "Output PostScript" pops up a dialog box which can be used to output a description of the machine in the PostScript language. The page output can be portrait or landscape in orientation, and can have a title.