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 .
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 non-deterministic 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 non-deterministic automata requires that some computation accepts the input. Alternating automata also provide a dual notion, where for acceptance all non-deterministic 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
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.
FSMs can only recognize regular languages, and hence they are not Turing-complete.
For each non-deterministic FSM, a deterministic FSM of equal computational power can be constructed with an algorithm.
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
In hardware a FSM may be built using a programmable logic device, gates and flip-flops or even relays.
More specifically, hardware implementation requires flip-flops 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.
Following concepts are commonly used to build software applications with finite state machines:
AT&T FSM Library™  http://www.research.att.com/projects/mohri/fsm/
- AutoFSM  http://autogen.sourceforge.net/autofsm.html
- Bandera  http://bandera.projects.cis.ksu.edu/
- Covered  http://covered.sourceforge.net/
- Dynamic Attachment Finite State Machine (DAFSM)  http://dmabco.sourceforge.net/
- Exorciser  http://www.educeth.ch/compscience/exorciser/
- Finite State Kernel Creator  http://fskc.sourceforge.net/
- Finite State Machine Editor  http://fsme.sourceforge.net/
- Finite State Machine Explorer  http://www.belgarath.org/java/fsme.html
- FSMGenerator  http://fsmgenerator.sourceforge.net/
FSA Utilities  http://odur.let.rug.nl/~vannoord/Fsa/
- JFLAP  http://www.cs.duke.edu/~rodger/tools/jflap/
- jrexx-Lab  http://jrexx.karneim.com/project02/project02.htm
- Kara  http://www.educeth.ch/compscience/karatojava/
- Nunni FSM Generator  http://nunnifsmgen.nunnisoft.ch/en/
- Petrify  http://www.lsi.upc.es/~jordic/petrify/petrify.html
- Qfsm  http://qfsm.sourceforge.net/
- Ragel  http://www.elude.ca/ragel/
- Statestep  http://statestep.com/
- StateWORKS http://www.stateworks.com/
- WhatOS  http://www.sticlete.com/whatos/
- Xerox Finite-State Software Tools  http://www.xrce.xerox.com/competencies/content-analysis/fssoft/home.en.html
- Timothy Kam: Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
- Tiziano Villa: Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
- Description from the Free On-Line 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: 02-09-2005 09:01:12
Last updated: 05-03-2005 17:50:55