CIT 594 Assignment 8: Automata
Spring 2010, David Matuszek
In this assignment you will implement a very simple type of "computer" with a complex name, a nondeterministic finite-state automaton (NFA). NFAs are graph structures.
The purpose of an NFA is to "accept" or "reject" an input string, very like a tokenizer. In fact, tokenizers are usually written as deterministic finite-state automata.
If you have not already done so, implement an API for graphs. You can use the one from my slides, or one of your own. Just about any graph implementation will do, as long as both nodes and edges may have associated values. You should not modify or adapt the graph API in any way to be specific to this problem; all necessary data can be carried in the node and edge values.
Name your main class
NFA. Use the Graph API to construct the NFA graph and "walk" it to process
Your program should use a GUI, rather than do text output. The GUI doesn't need to be very complicated.
An automaton can be represented as a graph, with the nodes representing "states" of the automaton, and the edges representing "transitions" between states. Here are the usual conventions for drawing automata:
|The (one) start state is indicated by an arrow pointing to it. This arrow does not indicate an edge in the graph!||Transitions are represented by labeled edges. The label on the edge indicates which input will cause the transition to occur.||Final states are represented by double circles. (Think of these as "goal nodes.")|
Here's how a deterministic finite-state automaton (DFA) works. For each new input sequence,
In a DFA, at each node there will be at most one outpointing edge with any given label. That means that the next state is completely determined by the input.
In an NFA,
EMPTY, meaning that following them is optional. Following the edge (or not following it) does not use up an input symbol; and
You will need to read in a description of an NFA and construct the corresponding graph. Here is an example of the input:
STATE q0 q1 q2 SYMBOL + - 9 TRANSITION q0 + q1 q0 - q1 q0 EMPTY q1 q1 9 q2 q2 9 q2 START q0 FINAL q2 INPUT 9 9 9 INPUT + 9 + 9
Here is a more precise definition of the required input:
FINALdenote sections of the input that describe the NFA. They must all occur, and must occur in this order. These words cannot be used as the names of nodes or the labels on edges.
INPUTdoes not describe the NFA, but rather input that is given to the NFA.
STATEis the name of a node on the graph.
SYMBOLis an allowable edge label. Edge labels may be used on as many edges as desired.
TRANSITIONmust be in groups of three, and each group describes a directed edge on the graph, in the order: Name of source node, edge label, name of destination node.
EMPTYmay be used to denote an "empty transition."
START; it is the name of the start state (node).
FINAL; these are the final states. (Note: It is possible for the start state to also be a final state.)
INPUTdenotes a series of zero or more
SYMBOLs to be given to the automaton to recognize.
INPUTmay occur more than once; each occurrence provides a separate, independent sequence of symbols to be given to the automaton. (In other words, finish processing the old input, clear everything, and start again at the start state with the new input.)
STATE. When you see this word, throw away the old graph and reinitialize everything.
I'm trying to be very precise about the form of the input file, because your input method will need to be able to read our test cases. I will also supply some sample input data. We will test with correct input, so checking the input for errors, although always desirable, is not a requirement.
JFileChooser to choose an input file to execute. Allow the
user to do this as many times as he/she likes without having to restart your
After reading in the graph, display it (as text, not as a drawing) in the GUI.
For each input, display the input, test whether the input is accepted by the NFA, and display the result (whether accepted or rejected).
If the input is accepted, display a trace of the successful path taken. A trace consists of a sequence of node and edge labels (or equivalently, a sequence of node labels alternating with inputs). For example:
+ 9 9
q0 + q1 9 q2 9 q2
To simplify the assignment, you can assume that there will be no cycles in the graph that contain only empty transitions. In other words, you don't have to worry about getting into an infinite loop; the only way you can get from a node back to itself is by consuming at least one input symbol.
When you start processing an input, you are in a single Thread. When you reach a node where a decision must be made (either because there is an empty transition, or because there is more than one transition possible for the current input symbol), don't decide. Instead, create and start additional Threads as needed, so that the program can follow all possible paths simultaneously.
Remember, an NFA succeeds if any path succeeds (ends in a final state after processing the last input symbol). When this happens, the successful Thread should report the path that it found, and should signal all other path-following Threads to terminate.
A Short Course on Thread Safety
"Testing can show the presence of bugs, but never their absence." -- Edsger W. Dijkstra
Try to make your program thread-safe. If your program is not thread-safe, it will probably still work. It might work for you but not for us. Concurrent threads execute in an unpredictable order, and exhaustive testing is essentially impossible. Dijkstra's comment applys in full force to concurrent programs, so correctness depends much more on a very careful, disciplined approach to programming, than on testing.
Name your project NFA. It should contain a package named
graph and a package named
nfa package should contain a class named
NFA containing the "main" method.
You should JUnit test what you reasonably can--at least the Graph API. (Hopefully, you've already done that!) It isn't obvious (to me) how to test methods that create or manipulate Threads, so you can skip those.
All classes and methods should have Javadoc comments (even if you are using methods that I wrote). Objects that need to be treated as immutable should be described as such in a Javadoc comment. Objects that require synchronized access must be described as such.
All the usual style rules apply (of course).
Tuesday, April 27, before midnight. No extensions except for serious
reasons. Turn in the complete project (including both
packages) in the usual way (zipped, via Blackboard). Late points will apply as usual, except that at some unspecified time (specifically, once we grade them) we will stop accepting programs.