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.
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.
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.
Some observations over this machine.
- It consists of two states, “on” and “off”. This machine can therefore be in exactly one of the two states at any point in time. In other words, the transitions between states are instantaneous.
- The “flick” event causes it to transition between states.
- When the machine enters the “on” state, a side effect occurs. A light is turned on.
- When the machine exits the “on” state, another side effect occurs. A light is turned off.
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:
- One state is defined as the initial state. When a machine starts to execute, it automatically enters this state.
- Each state can define actions that occur when a machine enters or exits that state. Actions will typically have side effects.
- Each state can define events that trigger a transition.
- A transition defines how a machine would react to the event, by exiting one state and entering another state.
- A transition can define actions that occur when the transition happens. Actions will typically have side effects.
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:
- The event is checked against the current state’s transitions.
- If a transition matches the event, that transition “happens”.
- By virtue of a transition “happening”, states are exited, and entered and the relevant actions are performed
- The machine immediately is in the new state, ready to process the next event.