A

David

Darling

finite-state automaton

Classes of automata.

Classes of automata.


Example of a state diagram.

The automaton described by this state diagram starts in state S1, and changes states following the arrows marked 0 or 1 according to the input symbols as they arrive. The double circle marks S1 as an accepting state. Since all paths from S1 to itself contain an even number of arrows marked 0, this automaton accepts strings containing even numbers of 0s.


A finite-state automaton (FSA) is the simplest computing device. Although it is not nearly powerful enough to perform universal computation, it can recognize regular expressions.

 

Finite-state automatons are defined by a state transition table that specifies how the FSA moves from one state to another when presented with a particular input. FSAs can be drawn as graphs.