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.

What are they?

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: 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 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. 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 regular expression 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.

Finite automata

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: a finite non empty set of states an initial state a finite non empty set of distinct input events or their categories state transitions actions 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. 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.

Definition

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.

opened closed pass closed   coin   opened

Diagrams etc.

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.

Harel statecharts

References

Need to relax? Try brain teasers. I would recommend those marked 'cool'.