Finite State Machine

  Although basically mostly a formal concept like the Turing machine, finite state machines do have some applications. A finite state machine consists of

• a set of states,
• an input alphabet (tokens),
• a transition function for each state, mapping tokens to other states.

Some of the states are terminal, like ``accept'' or ``reject'', thus have no output to other states. Other than the transition functions, a finite state machine has no memory.

Finite state machines may be used to classify items, or to find a string of tokens in an input stream.