If you are working as a developer (software engineer, coding wizard, or whatever you want to call it), chances are high you came across the term state machine. But do you also know what they are? Can you explain them to others? What is a statechart? This article is here to answer exactly these questions.
If you are here for fancy code in a specific language using a specific library you are wrong. This will be more about theory and will be language and library agnostic. This is also not about praising state machines or about their various benefits (even though they are great!). These topics will be part of follow-up articles. The "What are they?" will be more than enough for one article, you will see. Let's get started.
What are State Machines?
What actually is state in the context of state machines? Think of it as a status or mode of a system. Let us take a simplified oven as an example. It can have the states off and heating. The temperature of the oven is NOT the state. A state is something qualitative, not quantitative, and it is finite. Therefore the term state as used in frameworks like React or Vue is different from state in state machines. In React you would also refer to something like a searchTerm as state, but that would not be a state in a context of a state machine (there are infinite variations of possible searchTerms; a state would be something like idle, searching etc.).
Maybe you have also heard about Finite State Machines (FSM)? Have you googled "state machines" before? FSMs will be all over the place. This is how it looks like:
Ok fine, but what is the difference between state machines and finite state machines? It is rather obvious: it's the word "finite". FSMs are a subset of state machines. There are also possibly infinite state machines (like the Turing Machine). BUT almost always if someone is talking about state machines the person is in fact talking about FSMs. The Google search should already prove that point, right? Also, Wikipedia redirects you to the FSM article if you search for "state machines". And let's be honest, a person talking about something like a Turing Machine will most probably let you know 😉 Therefore I will from now on also use state machines and FSMs interchangeably.
Finite State Machines (FSM)
With the terminology about state machines and FSMs out of the way let us now answer the question about what FSMs actually are.
An FSM is a mathematical model of computation. It is always exactly in one state at a time. And, as the name suggests, consists of a finite number of states. FSMs are part of the automata theory. They are also called finite state automata (FSA).
I can already hear you thinking that this is being way too theoretical. It is getting more practical now. Let me show you the different parts of a state machine using a state(-transition) diagram showcasing the behavior of a video player:
This diagram depicts all mandatory parts of an FSM: There are three different states (stopped, playing, paused) whereas stopped is the initial state. There are multiple transitions between states. A transition is a function that determines the next state based on the current state and an event (f(currentState, event) = nextState), e.g. being in the playing state and receiving a pause event would lead to a transition to the paused state.
It is worth mentioning that this has the result that there is no next state (and therefore no transition) if the current state does not react to the given event. Given being in the stopped state and receiving a pause event, we would stay in the stopped state (f(stopped, pause) = stopped).
These are the mandatory building blocks of a state machine:
- finite, non-empty set of states
- initial state
- finite, non-empty set of events (aka input alphabet)
- transitions (aka state-transition function)
Optionally there are zero or more final states, which are states without any outgoing transitions, meaning there is no possible next state (therefore final).
Remember state machines being a mathematical model? This is how you would define the aforementioned using math:
That is already a very good foundational knowledge about state machines. There is more to it, like different classifications (deterministic vs. non-deterministic and Moore machines vs. Mealy machines), but I would consider them as extended knowledge. Therefore I will not go into details here. Let's answer the next question with more practical use: What are statecharts?
Statecharts
Okay great, that's it about state machines, but what are statecharts? State machines are helpful, but they can get very complex and lack some functionality. Imagine the video player example above would be extended to also include whether the player is maximized or not. You would have to duplicate the states to something like playing maximized, stopped maximized, and so on. Can you imagine how wild this would get with complex systems? There is even a term for that: state explosion (aka exponential blow-up problem). But don't worry, statecharts to the rescue. To describe the need for statecharts with the words of its inventor David Haral (therefore they are also known as Harel statecharts):
However, it is also generally agreed that a complex system cannot be beneficially
described in this naive fashion [referring to FSMs], because of the unmanageable, exponentially growing multitude of states, all of which have to be arranged in a ‘flat’ unstratified fashion, resulting in an unstructured, unrealistic, and chaotic state diagram.
(taken from STATECHARTS: A VISUAL FORMALISM FOR COMPLEX SYSTEMS by David Harel from 1987
Statecharts are an extension to state machines. They extend state machines with various features. Some of them are (the list is not exhaustive):
- Hierarchical states (aka nested states)
- Orthogonal states (aka parallel states)
- History state
- Conditions (enabling guarded transitions)
- Actions (aka outputs)
I would refer to hierarchical and orthogonal states as the main features because they are directly tackling the problem of state explosion.
I'll explain the aforementioned features by extending our video player example:
Please note that this is a simplified example. It is missing crucial parts like some kind of an error state.
Hierarchical States
I extended the example with the concept of the player being loaded. Therefore I added a new loading state and a loaded state containing the logic from the first example. We refer to loading as an atomic state (or simple state) and to loaded as a compound state (a state having nested states). We refer to loaded as a parent state of stopped. Whereas stopped is a sub-state of loaded (ignoring the window part for now).
The compound state behaves just like a statechart on its own. Entering a compound state always means also entering one of its sub-states (remember a state machine always being in a state). Think of the semantics of loaded like an XOR. loaded itself is always in a single state.
Hierarchical states allow us to cluster states and to zoom in and zoom out on the level of detail. loaded is an abstraction of details. We could zoom out by just hiding the content of loaded and only looking on a more abstract level on the loading and loaded state without caring about the sub-states of loaded.
Also, note the transition from loaded to loading with the reload event. This means that our machine would always transition from loaded to loading on receiving the reload event no matter in what sub-state of loaded it is in.
Orthogonal States
Orthogonal states are depicted by a dashed line. loaded has an orthogonal (or parallel) state describing the play AND window component (or orthogonal region). The "AND" is important here. It refers to the logical AND (in contrast to the XOR above). We are always in a state of all the orthogonal components at a time. Therefore we would refer to the substate of loaded like (stopped, minimized) as a single state (remember a hierarchical state always being a single state). We would say "The video player is in the stopped, minimized sub-state of loaded" or "The video player is in the minimized state of the window component". A component also acts like a statechart on its own.
Orthogonal states reduce the required states. Without it, we would need a single state for all possible combinations of the play and window component states.
History
History is a useful concept for nested states. You can see an example of that in the window component. With a history state, you remember the last state. In our example we would end up in (stopped, maximized) if we enter loaded again and have previously left it in the window components maximized state.
If we enter loaded for the first time we would end up in the (stopped, minimized) sub-state. With the introduction of the history state, the initial state is often also referred to as default state, because it will only be transitioned to if there is no previous history or no history state at all.
Conditions
Conditions are enabling guarded transitions. A transition only happens if the condition is fulfilled. In our example, it is only possible to enter maximized if play is in playing. If the machine would receive a maximize event but the player is stopped nothing would happen. In this example, a condition is enabling us to synchronize parallel states.
In addition, conditions allow us multiple outgoing transitions for the same event and state (all but one has to have a condition). For example, conditionally transitioning to a light or dark mode based on user preferences.
Actions
Actions are outputs of your statecharts. They are side-effects allowing us to interact with the world outside of the machine itself or to send events to the machine. They are instantaneous and ideally take zero amount of time (you are not waiting for something to be finished, e.g. a request to respond). Think of actions like "fire and forget".
Actions can happen in three different scenarios: entering a state, exiting a state, or when transitioning. I included examples for all of those in the video player. When entering loading we fire the showLoadingIndicator action and when exiting that stat we would fire hideLoadingIndicator (This is probably not what you would do, because you could just show the loading indication by checking the state. But you could do it this way and I was lacking a better example). Also, for the transitions of the play events, I added the start action. This action could send a signal to an actual video player implementation.
Wow, that was more than I thought myself beforehand 😅 Even though it is by no means complete. There are a lot of nuances to the mentioned features and even more features (like actions, delays and timeouts, and much more). But by now you should be familiar with the most important concepts.
Conclusion
State machines are great but they are much more powerful (and useful) when they are extended by the stateschart features. In fact, often people talking about state machines are referring to FSMs or even statecharts (also myself).
There was a W3C standard created (after about ten years of work): State Chart XML (SCXML): State Machine Notation for Control Abstraction. You can check it out if you are interested in the details. Also, I recommend checking out statecharts.dev. They also have a nice glossary.
I hope this article was useful for you. I will follow up with articles about the benefits of state machines and their actual implementation using XState in TypeScript - I promise. You could help to make the world of developers a better place by sharing your knowledge about state machines.
Ressources
National Institute of Standards and Technology
Wikipedia: Finite State Machines
STATECHARTS: A VISUAL FORMALISM FOR COMPLEX SYSTEMS by David Harel from 1987
Top comments (0)