Skip to content
memoDwarves Foundation

Research notes/Architecture

State explosion in state machines and how statecharts solve it

Learn how statecharts solve the state explosion problem in state machines using parallel states, hierarchical states, and guard conditions for simpler and more efficient designs.

Written 4 years ago. Check versions before you rely on it.

What is state explosion?

The main problem that’s stopping widespread usage of state machines is the fact that beyond very simple examples, state machines often end up with numerous states, a lot of them with identical transitions. Statecharts solve this state explosion problem.

State explosion

Similar to nested positive if statements, state explosions represent combinatorially complex growth of states. This can also be seen with nested Product types.

How do statecharts solve this problem?

Parallel states

Separating nested finite states into individual states that can be progressed with the same or different events:

Parallel state machine

Hierarchical states

Reorganizing nested finite states into a hierarchy, such that the finite state of a child state machine is dependent on the transition between the parent and child machines:

Hierarchical state machines

Guards (conditions)

Guards here serve as a pre-condition to a transition, which essentially prevents a transition from occurring based on a condition:

Guard conditions

Reference