What is a state machine?

Wikipedia defines a finite-state machine (FSM) as:

an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition.

And further:

A state is a description of the status of a system that is waiting to execute a transition.

A state machine is also a visual depiction of such an abstract machine.

Example

Here is a visual depiction of a simple state machine. It is a model of a simple on/off switch.

A simple on/off switch with two states. A state machine with two states, "on" and "off", the "flick" event transitioning between them. The On state defines actions to turn a light on and off on entry and exit, respectively

Some observations over this machine.

This simple state machine is comparable to a boolean variable—which can either be true or false—that controls the on-ness of something.

What is state anyway?

Program state is the set of all variables in a program and their values at any point in time (see Wikipedia). A program or software component that has five independent variables, that each could be true or false, then it could in theory be in any of 32 states (2 to the power of 5 = 32). However, a program will often have invalid states, and in traditional software, the variables are carefully checked and manipulated in such a way that these invalid states don’t happen.

A state machine is an alternative way of modeling program state: Instead of defining independent variables, a machine is crafted specifically to handle what states are possible, and when a machine is a given state, what next state is allowed. Those five independent boolean variables are replaced with a single state machine which intrinsically can only be in valid states.

Relationship with statecharts

Understanding state machines is almost the same as understanding statecharts. In many ways, statecharts are the “bigger brother” of state machines, designed to overcome some of the limitations of state machines.

State machines are closely related to their bigger brother, statecharts. A statechart is essentially a state machine that allows any state to include more machines, in a hierarchical fashion. This is to overcome some of the limitations that are inherent to state machines.

The primary goal of statecharts.github.io is to help you to understand statecharts. An understanding of state machines is a nice side effect. What is a statechart?

Abstract machine vs run-time

An important distinction must be made between the abstract machine itself (e.g. the drawing of a state machine, or the code) and the more concrete run-time execution of a particular abstract machine. This distinction is similar to the difference between a class (abstract definition) and an object (concrete instantiation). Similarly, for a single abstract machine, there may be many executions, just as there are often many instances of any particular class.

The terms “statechart”, “state machine” and “FSM” are often used to mean both the abstract and run-time form, although the run-time form sometimes has the qualifier “run” or “execution”, as in “state machine execution” or “statetchart run”.

An abstract state machine is a software component that defines a finite set of states:

When “running” a state machine, this abstract state machine is executed. The first thing that happens is that the state machine enters the “initial state”. Then, events are passed to the machine as soon as they happen. When an event happens:

Further reading