In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. The internal states of the machine carry no further structure. FSMs are very widely used in modelling of application behaviour, design of hardware digital systems, software engineering, study of computation and languages .
Overview
It can be represented using a state diagram. There are finitely many states, and each state has transitions to states. There is an input string that determines which transition is followed (some transitions may be from a state to itself). Finite state machines are studied in automata theory, a subfield of theoretical computer science.
There are several types of finite state machines including
 Acceptor s a.k.a. Recognizer s: They either accept/recognize their input or do not.

Transducers: They generate output from given input.
Finite automata may operate on languages of finite words (the standard case), infinite words (Rabin automata , Büchi automata), or various types of trees (tree automata), to name the most important cases.
A further distinction is between deterministic and nondeterministic automata. In deterministic automata, for each state there is exactly one transition for each possible input (DFA). In nondeterministic automata, there can be none or more than one transition from a given state for a given possible input (NFA, GNFA). Nondeterministic automata are usually implemented by converting them to deterministic automata—in the worst case, the generated deterministic automaton is exponentially bigger than the nondeterministic automaton (although it can usually be substantially optimised).
The standard acceptance condition for nondeterministic automata requires that some computation accepts the input. Alternating automata also provide a dual notion, where for acceptance all nondeterministic computations must accept.
Apart from theory, finite state machines occur also in hardware circuits, where the input, the state and the output are bit vectors of fixed size (Moore machines and Mealy machines).
Mealy machines have actions (outputs) associated with transitions and Moore machines have actions associated with states.
Types of machines
Acceptors and recognizers
Transducers
Optimization and canonicalization
The problem of optimizing an FSM (finding the machine with the least number of states that performs the same function) is decidable, unlike the same problem for more computationally powerful machines. Furthermore, it is possible to construct a canonical version of any FSM, in order to test for equality. Both of these problems can be solved using a colouring algorithm.
Computational power
FSMs can only recognize regular languages, and hence they are not Turingcomplete.
For each nondeterministic FSM, a deterministic FSM of equal computational power can be constructed with an algorithm.
Implementation
Definition
A finite state machine is a model of a control application. It describes the system behaviour using states, transitions and actions.
The state stores information about the past, i.e. it reflects the input changes from the system start to the present moment.
A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition.
An action is a description of an activity that is to be performed at a given moment. There are several action types:
 Entry action: execute the action when entering the state
 Exit action: execute the action when exiting the state
 Input action: execute the action dependant on input conditions
 Transition action: execute the action when performing certain transition
Hardware Applications
In hardware a FSM may be built using a programmable logic device, gates and flipflops or even relays.
More specifically, hardware implementation requires flipflops to store state variables, a block of combinational logic which determines the state transition, and a second block of combinational logic that determines the output of a FSM.
Software Applications
Following concepts are commonly used to build software applications with finite state machines:
Tools

AT&T FSM Library™ [1] http://www.research.att.com/projects/mohri/fsm/
 AutoFSM [2] http://autogen.sourceforge.net/autofsm.html
 Bandera [3] http://bandera.projects.cis.ksu.edu/
 Covered [4] http://covered.sourceforge.net/
 Dynamic Attachment Finite State Machine (DAFSM) [5] http://dmabco.sourceforge.net/
 Exorciser [6] http://www.educeth.ch/compscience/exorciser/
 Finite State Kernel Creator [7] http://fskc.sourceforge.net/

 Finite State Machine Editor [8] http://fsme.sourceforge.net/
 Finite State Machine Explorer [9] http://www.belgarath.org/java/fsme.html
 FSMGenerator [10] http://fsmgenerator.sourceforge.net/

FSA Utilities [11] http://odur.let.rug.nl/~vannoord/Fsa/
 JFLAP [12] http://www.cs.duke.edu/~rodger/tools/jflap/
 jrexxLab [13] http://jrexx.karneim.com/project02/project02.htm
 Kara [14] http://www.educeth.ch/compscience/karatojava/

 Nunni FSM Generator [15] http://nunnifsmgen.nunnisoft.ch/en/
 Petrify [16] http://www.lsi.upc.es/~jordic/petrify/petrify.html
 Qfsm [17] http://qfsm.sourceforge.net/
 Ragel [18] http://www.elude.ca/ragel/
 Statestep [19] http://statestep.com/
 StateWORKS http://www.stateworks.com/
 WhatOS [20] http://www.sticlete.com/whatos/
 Xerox FiniteState Software Tools [21] http://www.xrce.xerox.com/competencies/contentanalysis/fssoft/home.en.html

See also
References
 Timothy Kam: Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0792398424
 Tiziano Villa: Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0792398920
External links
 Description from the Free OnLine Dictionary of Computing http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=finite+state+machine
 Citations from CiteSeer http://citeseer.org/cs?q=finite+state+machine
Last updated: 02092005 09:01:12
Last updated: 05032005 17:50:55