finite-state automaton

A finite-state automaton is the simplest computing device. Although it is not nearly powerful enough to perform universal computation, it can recognize regular expressions. Finite-state automatons (FSAs) 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.