<mathematics, algorithm> (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 is one where the next state is uniquely determinied by a single input event. A nondeterministic FSM may have several next states for a given input event, which one is actually chosen may either be random or, according to a different definition, it may depend on an arbitrary number of subsequent input events. In the latter case, until these subsequent events occur it is not possible to determine which state the machine is in. It is possible to automatically translate a nondeterministic FSM into a deterministic one which will produce the same output given the same input.
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].
(12 Apr 1995)