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 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
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 Turing-complete.
For each non-deterministic 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 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.
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/
- jrexx-Lab [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 Finite-State Software Tools [21] http://www.xrce.xerox.com/competencies/content-analysis/fssoft/home.en.html
|
See also
References
- 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
External links
- 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
