# finite-state automaton

Classes of automata.

The automaton described by this state diagram starts in state S_{1}, and changes states following the arrows marked 0 or 1 according to the input symbols as they arrive. The double circle marks S_{1} as an accepting state. Since all paths from S_{1} 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.