A Finite State Machine (FSM) is an abstract machine that can be used to design software components. In this post, we will introduce the representation of FSMs we use at wisol. In following posts, we will focus on more detailed aspects, practical applications, and describe our free C++ implementation.
Main Advantages
A FSM can model many problems, including communication protocols, language parsing, or general behaviour of a software component. From an engineering point of view, using an FSM to design a component has a few specific advantages. These advantages make FSMs an important concept in the software domain.
- A state machine diagram is the documentation of the component being modelled.
- It is difficult or impossible to diverge from the model when used correctly (i.e. generating the code or using a generic implementation).
- It is easier to reason about a component using a model (e.g. a diagram).
- It makes the complexity (or the simplicity) of a component more visible.
There may be other advantages, but in our experience, the above seem to be very important ones.
State Machine Components
There are different representations of the state machine concept. We focus on a clean and simple representation.
A state machine consists of the following elements.
- An initial state.
- A (possibly empty) set of final states.
- A finite, non-empty set of states.
- A set of state transitions (actions).
A state change is initiated by an event sent to the state machine, and can optionally be guarded by a function. Whether a transition is taken therefore depends on the current state and the return value of the guard function. If a transition is taken, its actions are executed.
Example
As an example, consider a state machine that models a motor that is operated by a button. In addition, the motor is only allowed to run in a given temperature range.
This state machine, although very simple, shows most of the elements of a state
machine. Its initial state is state MotorOff. It can then transition to state
MotorOn when the button is pressed. However, this transition is guarded by a
check for the temperature. When in state MotorOn, the motor is switched off
by either pressing the button again, or when an over temperature condition is
detected.
Semantics
It is important to define the semantics of an implementation of a FSM. For our representation, the following procedure is executed whenever an event is received by a machine.
- Consume a event.
- Check if the event potentially initiates a transition from the current state. Otherwise return.
- For each transition found, check if its guard evaluates to
true. Return if none is found. - Execute the actions of one (and only one) of the selected transition.
- Change current state to the state where the transition points to.
Other representations
As mentioned above, there exist different representation of the state machine concept. Most notably the UML state machine. It enhances the basic concept with hierarchical nested states, orthogonal regions, as well as entry and exit actions. All these concepts have their place and are useful in certain circumstances. However, they also make it more difficult to understand, and its semantics are sometimes unclear.
The representation described above does not implement most of these extended features. However, it does have the characteristics that actions depend on the current state of the system and the trigger event. In our experience, this simple representation gives enough benefit in practice, without being difficult to understand or implement.