Java Glossary : finite state automaton

Java definitions: 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

You are here : home : Java Glossary : F words : finite state automaton.

finite state automaton

A finite state automaton is a way of looking at a computer, a way of solving parsing problems, and a way of designing special purpose hardware. The automaton at any time in is one of a finite number of internal states. It is a black box. You feed it input, usually a character at a time. It turns its internal crank and applies its rules and goes into a new state, and accepts more input. Every once in a while it also produces some output. A simple parser might classify Java source as either java commands or comment. It would have states for having seen /, //, /*, /* ... *, /* ... */ etc.

Lexers and regex packages are tools for creating finite state automatons.

One way of writing finite state automata is 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.

CHSM ¤ lexer ¤ regular expressions

home	Canadian Mind Products
	mindprod.com IP:[24.87.56.253]
	Your IP:[80.134.30.163]
	You are visitor number 1054.
	Please send errors, omissions and suggestions
	to improve this page to Roedy Green.
	You can get a fresh copy of this page from:	or possibly from your local J: drive mirror:
	http://mindprod.com/jgloss/finitestate.html	J:\mindprod\jgloss\finitestate.html