CIT 594 Assignment 8: Automata
Spring 2010, David Matuszek

Purpose

To give you more experience with graphs.
To give you more experience with GUIs.
To give you some experience with Threads.

General idea

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 input.

Your program should use a GUI, rather than do text output. The GUI doesn't need to be very complicated.

All about automata

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,

Set the "current state" to the start state.
For each symbol in the input,
1. If there is an outpointing edge from the current state with that symbol as a label, follow the edge to get the new current state.
2. If there is no outpointing edge from the current state with that symbol as a label, terminate and reject the input.
When all symbols have been read, accept the input if the current state is a final state, and reject the input if it is not.

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,

There may be more than one outpointing edge with any given label. That means that any one of these edges may be followed.
Some edges may be labeled with EMPTY, meaning that following them is optional. Following the edge (or not following it) does not use up an input symbol; and
The input is accepted if any sequence of choices leads to a final state.

Details of this assignment:

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:

STATE, SYMBOL, TRANSITION, START, and FINAL denote 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.
INPUT does not describe the NFA, but rather input that is given to the NFA.
Each word following STATE is the name of a node on the graph.
Each word following SYMBOL is an allowable edge label. Edge labels may be used on as many edges as desired.
Words following TRANSITION must 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.
- In addition, the edge label EMPTY may be used to denote an "empty transition."
Exactly one node name must follow START; it is the name of the start state (node).
Zero or more node names may follow FINAL; these are the final states. (Note: It is possible for the start state to also be a final state.)
INPUT denotes a series of zero or more SYMBOLs to be given to the automaton to recognize.
The word INPUT may 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.)
Capitalization is significant.
Whitespace is not significant, except to separate words.
"Words" may be composed of any non-whitespace characters.
Input may consist of more than one NFA. Each will be started by the word 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.

Use a 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 program.

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:

Input: + 9 9

Trace: 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.

Threads

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

Immutable data is thread-safe. If your NFA cannot change while you are using it, and your input data to the NFA cannot change while you are stepping through it, then these are thread-safe.
ALL accesses to mutable data must be synchronized. This includes reads as well as writes. You must use synchronization to save and to display any solution you find.
Values strictly local to a method are thread-safe. This is because every entry to a method gets a new set of local variables. However, local references to external data are not thread-safe. Any values that may "escape" the method are not thread-safe. Only values contained entirely within the method are thread-safe.

"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.

Package structure

Name your project NFA. It should contain a package named graph and a package named nfa. The nfa package should contain a class named NFA containing the "main" method.

Other considerations

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).

Due date:

Tuesday, April 27, before midnight. No extensions except for serious reasons. Turn in the complete project (including both nfa and graph 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.