finite state automaton : Java Glossary

Implementations

In the days of C, the state was stored as an integer 0 .. n. You had a complicated nest of switch statements that examined both the current state and the input to determine the next state.

In 1.4-, one way of writing finite state automata was to have a singleton class represent each possible state. There is a state variable that represents the current state. You feed the input to a standard method of the class’s interface and it computes the next state. That way states that are very similar can inherit default behaviours. You can have a static method to categorise the input, and and a separate instance method to handle each categroy, or use a common method and a switch to dispatch to code based on input category to decide the next state. You don’t need any switch code based on current state. The dynamic method overriding features of Java handle that.

In JDK 1.5+, one way to write finite state automata is to use an enum constant to represent each state. A custom next method on each enum constant examines the input and calculates the next state. The various parsers used by JDisplay work using enums. The problem with this approach is you must use statics for variables shared between states. You can’t instantiate several different finite state automata.

Finite state automata come in two flavours: DFA Deterministic Finite Automaton and NFA Nondeterministric Finite Automaton. NFAs don’t always give the same answer.

You might wonder what use a non-deterministic program could be. Consider integration in two dimensions by the Monte Carlo method. All you need is a way of determining if a point is inside or outside the area you want to integrate. Then you generate random points and count how many are inside and how many outside. The ratio tells you the ratio of the area inside to outside which when applied to the total area gives you an approximation of the area of the region to integrate. You want a random pattern of test points. Any regular pattern could be thrown off by regularities in the shape of the region you are trying to integrate.

Strategy

1. You need two classes, both enums. One has an enum for each category of character input you process and a method for categorising characters. The other has one enum for each state. Each enum constant implements an abstract method called nextState that takes the category of the next character and the next character as parameters and returns the enum constant for the next state. The nextState method may emit output.
2. Typically a nextState method will have a switch based on the category of the incoming chararacter.
3. You start by removing complications to the problem, and working out the states and categories for just that simplification. Gradually add the complications which will usually require more categories and states.
4. If you see a combinatorial explosion in your number of states, factor your finite state automaton, and track its state with two or more different state variables, often using simple auxliliary booleans booleans.
5. Write explicit descriptions of what it means when you are in each of your states. Proofread by focusing on each state, and checking off the processing for each category of input, closing your eyes to everything else. It is amazing how easy it is to write code that works first time if you do this. Don’t use default to cover actual categories because it makes it too easy to forget a category.
6. Keep all your switch statements and states in standard order, usually alphabetical. This will make them easier to find, easier to compare, and easier to check for inadvertent deletions.
7. Don’t implement any auxiliary routines you need, just write stubs. You may find as you work out the implementation, that you will make drastic changes to these methods. There is no point in implementing them until the design specification settles down.
8. Write some unit tests for your various auxiliary routines.
9. Put debug code in your main driver routine to dump the current state, the next character and the category of the next character. Run your automaton through on various test cases, just looking for anomalies.
10. Proof read your state machine by looking for symmentries and repeating patterns. Make sure deviations from the symmetries are intentional.
11. Test on a small document that contains all the corner (pathological cases) you can think of.
12. Test on real world documents. I forgot all about comments in my HTML compactor finite state automaton on my first cut. I did not notice the problem until I started testing on real world documents.

Sample Code

Compactor: compacts a group of files, a single file or a string.

Books

	recommend book⇒Introduction to the Theory of Computation, Second Edition
		paperback	hardcover
	ISBN13:	978-0-534-95250-1	978-0-534-95097-2
	ISBN10:	0-534-95250-X	0-534-95097-3
	publisher:	Course Technology
	published:	2005-02-15
	by:	Michael Sipser
This is a university textbook that will explain such mysteries and finite state automata and how to convert them into regex expressions. It covers Turing machines. This is about the theory of computing, not a cookbook on how to code anything. This is thin but expensive book.
abe books.co.uk abe books.ca amazon.co.uk amazon.ca abe books.de chapters.indigo.ca amazon.de abe books.com abe books.fr amazon.com amazon.fr barnes and noble.com abe books.it powells.com iberlibro.com abe books anz