Dictionary.net

(FSM or "Finite StateAutomaton", "transducer") An abstract machine consisting ofa set of states (including the initial state), a set ofinput events, a set of output events, and a state transitionfunction. The function takes the current state and an inputevent and returns the new set of output events and the nextstate. Some states may be designated as "terminal states".The state machine can also be viewed as a function which mapsan ordered sequence of input events into a correspondingsequence of (sets of) output events.A deterministic FSM (DFA) is one where the next state isuniquely determinied by a single input event. The next stateof a nondeterministic FSM (NFA) depends not only on thecurrent input event, but also on an arbitrary number ofsubsequent input events. Until these subsequent events occurit is not possible to determine which state the machine is in.It is possible to automatically translate any nondeterministicFSM into a deterministic one which will produce the sameoutput given the same input. Each state in the DFA representsthe set of states the NFA might be in at a given time.In a probabilistic FSM [proper name?], there is apredetermined probability of each next state given thecurrent state and input (compare Markov chain).The terms "acceptor" and "transducer" are used particularly inlanguage theory where automata are often considered asabstract machines capable of recognising a language (certainsequences of input events). An acceptor has a singleBoolean output and accepts or rejects the input sequence byoutputting true or false respectively, whereas a transducertranslates the input into a sequence of output events.FSMs are used in computability theory and in some practicalapplications such as regular expressions and digital logicdesign.See also state transition diagram, Turing Machine.[J.H. Conway, "regular algebra and finite machines", 1971, EdsChapman & Hall].[S.C. Kleene, "Representation of events in nerve nets andfinite 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].