### state machine ==>

# Finite State Machine

<*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 is one where the next state is uniquely
determined by a single input event. The next state of a
non-deterministic 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 some (but not all)
non-deterministic FSMs into deterministic ones which will
produce the same output given the same input. [Is this true?]

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].

[FOLDOC]

<*2001-03-16*>

Try this search on OneLook / Google

**Nearby terms:**
finite differencing « Finite State Automata « Finite State Automaton « Finite State Machine » first-order » first-order logic » first-order predicate logic