Finite State Machine

Finite State Machine
acceptor
Finite Automata
Finite Automaton
Finite State Automata
Finite State Automaton
NFA

   <mathematics, algorithm, theory> (FSM or "Finite State
   Automaton", "transducer") An {abstract machine} consisting of
   a set of {states} (including the initial state), a set of
   input events, a set of output events, and a state transition
   function.  The function takes the current state and an input
   event and returns the new set of output events and the next
   state.  Some states may be designated as "terminal states".
   The state machine can also be viewed as a function which maps
   an ordered sequence of input events into a corresponding
   sequence of (sets of) output events.

   A {deterministic} FSM (DFA) is one where the next state is
   uniquely determinied by a single input event.  The next state
   of a {nondeterministic} FSM (NFA) depends not only on the
   current input event, but also on an arbitrary number of
   subsequent input events.  Until these subsequent events occur
   it is not possible to determine which state the machine is in.

   It is possible to automatically translate any nondeterministic
   FSM into a deterministic one which will produce the same
   output given the same input.  Each state in the DFA represents
   the set of states the NFA might be in at a given time.

   In a probabilistic FSM [proper name?], there is a
   predetermined {probability} of each next state given the
   current state and input (compare {Markov chain}).

   The terms "acceptor" and "transducer" are used particularly in
   language theory where automata are often considered as
   {abstract machines} capable of recognising a language (certain
   sequences of input events).  An acceptor has a single
   {Boolean} output and accepts or rejects the input sequence by
   outputting true or false respectively, whereas a transducer
   translates the input into a sequence of output events.

   FSMs are used in {computability theory} and in some practical
   applications such as {regular expressions} and digital logic
   design.

   See also {state transition diagram}, {Turing Machine}.

   [J.H. Conway, "regular algebra and finite machines", 1971, Eds
   Chapman & Hall].

   [S.C. Kleene, "Representation of events in nerve nets and
   finite automata", 1956, Automata Studies. Princeton].

   [Hopcroft & Ullman, 1979, "Introduction to automata theory,
   languages and computations", Addison-Wesley].

   [M. Crochemore "tranducters and repetitions",
   Theoritical. Comp. Sc. 46, 1986].

   (2001-09-22)