A Finite State Machine (FSM) is a model of behavior using states and state transitions.
A transition is a state change triggered by an input event, i.e.
transitions map some state-event pairs to other states.
As indicated in the name, the set of states should be finite.
Also, it is assumed that there is a finite set of
distinct input events or their categories (types, classes).
Subsequently, the set of transitions is finite as well.
FSMs are one of the most widely used models in computer programming in general.
In particular, FSMs are ubiquitous in programming embedded systems
and for describing digital circuits. Modeling by means of FSMs has been so successful that
they become adopted as a part of the Unified Modeling Language standard by Object Management Group.
The origin of FSMs is finite atomata.
A Finite Atomaton is a more formal notion than a FSM.
It is defined as a quintuple ( A, S, s, T, F ), where:
Finite automata are primarily used in parsing for recorgizing languages.
Input strings belonging to a given language should turn an automaton
to final states and all other input strings should turn this automaton
to states that are not final.
- A is a finite non empty set of symbols (input alphabet)
- S is a finite non empty set of states
- s is an initial state, an element of S
- T is the state transition function: T: S x A -> S
- F is the set of final states, which is a subset of S
Finite automata that additionally generate output are called transducers.
In order to define a transducer, an output alphabet and output function should be specified
in addition to the five components outlined earlier.
The output function can be a function of a state or a function of both state and input symbol.
If the output function depends on a state and input symbol, then it is called a
Mealy automaton. If the output function depends only on a state, then it called is a Moore automaton.
One of the most important facts about finite automata is that
instances of any
can be recognized by a finite automaton.
It is well-known how to build the recognizing automaton for a given regular expression.
Inversely, it is known how to construct a regular expression defining a language
recognized by a given finite automaton.
Automata theory studies properties of automata. For instance,
it investigates how to optimize automata. In addition to the finite atomata
defined above and which are also called deterministic finite automata,
there are non-deterministic finite automata. Automata theory also studies so-called
pushdown automata. All these topics are beyond the scope of this tutorial.
The notion of finite automata is mathematically rigorous. The notion of FSMs was introduced
as a less rigorous and more suitable for computer science.
A FSM is defined by the following:
As opposed to input symbols for finite automata,
any sequence of event can be a FSM input. In other words, any object can be an input entity.
The only restriction on input is that all possible inputs should be classified
as belonging to one of a finite number of distinct input categories (types, classes).
In many simpler cases, only a finite number of distinct input objects are allowed.
It is assumed that input events are then processed synchronously, that is,
the next event is processed only after the current event is fully consumed
and a transition is executed if necessary. This may require queing events
before the time comes to process them.
- a finite non empty set of states
- an initial state
- a finite non empty set of distinct input events or their categories
- state transitions
One other important difference between finite automata and FSMs is that
actions may be related to FSMs. The role of actions is to generate output.
FSMs may also communicate with other processes by means of actions.
Presumably, actions do not generate input events. In other words,
FSMs consume external events only.
Also, actions are stateless,
i.e. they cannot carry any information from one invocation to another.
Actions may be associated with transitions,
and if so, such FSM is called a Mealy machine. The FSMs in which actions are
associated with states are called Moore machines.
Since actions can be represented by virtually any program (code)
and action input can be any object,
the functionally of FSMs may be quite rich, going far beyond the limits
of finite automata.
FSMs are most commonly represented by state diagrams, which are also called
state transition diagrams. The state diagram is basically a directed graph where
each vertex represents a state and each edge represents a transition between two states.
Another common representation of FSMs is state transition tables. In these tables,
every column corresponds to a state, every row corresponds to an event category.
Values in the table cells give the states resulting from the respective transitions.
Table cells also can be used for specifying actions related to transitions.
FSM specifications are pretty simple and 'flat'.
Harel introduced hierarchical FSMs (statecharts) in which any state can be another FSM.
The aim of this extension is to reduce the size of FSM specifications.
In practice, the number of FSM transitions grows rapidly when the number of states grows.
This happens because it is necessary to copy existing transitions for newly introduced states.
The hierarchical FSMs solve this problem by bringing the possibility
to encapsulate newly introduced states within a FSM that corresponds to one state
of the next upper level. And the next-level transitions become applicable to the entire FSM
of this lower level. Yet another extension of FSMs is introduced by allowing
sequences of events to define transitions -
see this paper.
A. Aho, R. Sethi, J.Ullman Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1985.
Unified Modeling Language (UML)
Copyright © 2005 Alexander Sakharov
Need to relax? Try brain teasers. I would recommend those marked 'cool'.