An interactive introduction to the diagram that taught engineers how to draw a system with a million states without going mad.
Any system that reacts to events over time — a thermostat, a network protocol, an aircraft autopilot — can in principle be drawn as a finite-state machine: a set of states, and arrows showing which event moves you from one to another. The trouble is that "in principle" hides a combinatorial bomb.
Take something as pedestrian as a digital watch. It has a few independent things going on: which function it's in (time, stopwatch, alarm), whether the display is 12-hour or 24-hour, and whether the hourly beep is on or off. Each of those is a small, sensible idea on its own. But a flat state machine has to draw one node for every combination of them, because a state machine only knows about the system being in exactly one place at a time.
Every feature you add is a fact you and the rest of your team already understand independently — "the beep is on or off," full stop. A flat machine has to multiply that fact into every existing state. A statechart just adds it once. Toggle the features above and watch the two counts diverge.
This is not a made-up problem. It's why hand-drawn state diagrams for real systems — telecom switches, avionics, the reactive control software David Harel was building at the Israeli aircraft industry in the early 1980s — degenerated into what he called . In 1987 he published a fix, in a formalism he called the statechart, that let a diagram stay linear in complexity while the system it describes grows exponentially.
Three ideas do almost all of the work: hierarchy, orthogonality, and broadcast communication. Each one collapses a different kind of explosion.
The first idea is obvious once you see it: let a state contain other states.
Say the watch's Alarm function actually has three sub-steps — setting the hour, setting the sound, and confirming. In a flat diagram, every one of those three sub-steps needs its own copy of "if MODE is pressed, go back to Time," because the flat machine has no notion that they're all part of the same enclosing idea. Harel's fix is a superstate: draw a box around the three sub-steps, and let one arrow, drawn on the boundary of the box, mean "from anywhere in here."
Nothing about the behavior changed between the two views — from Time, pressing MODE always lands you in Set Hour, and from any of the three alarm substates, pressing MODE always returns you to Time. What changed is that the statechart only has to say that once. This is the same trick as a class hierarchy in software: define the common behavior on the parent, and every child inherits it without re-declaring it. Harel's superstates are, structurally, exactly that idea applied to states instead of objects.
Hierarchy handles nesting. It doesn't yet handle the other source of the explosion: independent things happening at once.
The watch's function (Time / Stopwatch / Alarm) and its backlight (Off / On) don't interact. A flat diagram still has to draw a node for every pair — (Time, Off), (Time, On), (Stopwatch, Off), and so on — because a flat state machine can only be in one place. Harel's second device is the AND-state: split a superstate into side-by-side orthogonal regions, each with its own little state machine running independently, separated by a dashed line. Being "in" the superstate now means being in one state from every region at once — but you draw each region only once, not once per combination.
Click a state in either region to activate it. The two regions never block each other — that's what "orthogonal" means here. The full system state is the pair of whatever's currently active in each region, but the diagram itself only has 5 nodes, not the 6 pairs a flat diagram would need — and the gap widens fast as you add more independent regions.
Orthogonal regions that never interact are a toy. Real independence is rarely total — one part of a system usually needs to nudge another.
Harel's third device is broadcast communication: any transition can, on top of changing its own region's state, emit an event. That event is broadcast to every other region in the chart simultaneously, and any transition anywhere else that's waiting on it fires too, in the same step. This is what lets orthogonal regions stay independent for drawing purposes while still being able to coordinate — a car's interior light doesn't need its own copy of the door sensor's logic, it just reacts to the event the door region already emits.
The door_opened event is emitted by the Door region's own transition, then broadcast — the Light region, which has a transition sitting idle and waiting for exactly that event, fires it on the same step, with no message-passing code and no shared variable between the two regions.
This is the mechanism that makes statecharts a genuine formalism for reactive systems rather than just a nicer drawing convention. Sequential programs compute an output from an input and stop; reactive systems live inside a stream of events indefinitely, and most of the interesting bugs in them are about which region finds out about which event, and in what order.
One more wrinkle. Ordinarily, re-entering a superstate drops you at its default substate, the same place every time — a small arrow with no source marks which child that is. But some systems need to resume, not restart.
Pause a washing machine mid-cycle and resume it, and it should pick the rinse step back up, not start over from wash. Harel's history connector (drawn as a circled H) marks a superstate as remembering the last substate it was in, so that re-entering through the history connector returns you there instead of to the default.
Hierarchy, orthogonality, and broadcast make a complex reactive system drawable. They don't, by themselves, make it correct — a beautifully organized diagram can still have a bug in it, and the bug is usually hiding in an interleaving of events nobody thought to trace by hand.
This is the gap that later tools built on statecharts have tried to close. P, developed originally at Microsoft Research and now used inside AWS to design services like S3, DynamoDB, and EBS, keeps the same core mental model — a system as a set of communicating state machines — but treats it as source code rather than a picture, and adds a checker that doesn't just draw the diagram, it exhaustively explores it.
Each machine is a state, an entry action, and event handlers — the same nodes and arrows as the diagrams above, just written down instead of drawn. send is P's version of broadcast, addressed to one machine instead of every region at once, which is what makes it possible to reason about who can receive what.
The payoff is the checker. Two machines exchanging even a couple of events already have several possible orders in which those events can arrive and interleave — and in a real system with dozens of machines, that number is astronomical. A test suite exercises a handful of orderings you thought to write. P's checker does a systematic search over the interleavings themselves, looking for any ordering that violates a stated correctness property, and hands back a reproducible trace when it finds one.
Client sends req then ack. Server sends ready then grant. The property being checked: req must never arrive before ready — otherwise the client's request is dropped on the floor.
This is a toy version of the same idea: at real scale, P's checker doesn't enumerate every interleaving explicitly — it explores the space directly and prunes as it goes — but the principle is identical. Instead of trusting the diagram, or trusting the handful of orderings a person thought to test, it goes looking for the ordering that breaks the property.
Everything so far has assumed you already have the diagram — you're either drawing it or writing it as P. Often you inherit a system with neither: no design docs, just a log of the events it happened to emit while running. The statechart was never written down. It exists only implicitly, in the shape of the traces the system produces.
Recovering a machine from example behavior is a synthesis problem in its own right, usually called specification mining or model inference. The classical approach, , is a direct implementation of an old idea from automata theory: a "state" is nothing more than an equivalence class of histories that all predict the same future. Group the trace by the last k events it saw, ask what tends to happen next after each group, and use that as a stand-in for "which state was the system in." The question that actually matters is how big k needs to be before those groups stop being wrong.
A hidden system emits ok, fail, and reset events, and locks out after a second consecutive failed login until a reset clears it. You aren't told any of that — only the trace below.
At k=0, with no context at all, the best you can do is always guess the single most common event — barely better than a coin flip. At k=1, the last event helps a little, but a lone fail is ambiguous: it could be a first slip or the one that's about to trigger a lockout, and those two cases call for opposite predictions. Move to k=2 and accuracy jumps — the last two events are enough to tell "one strike" from "two strikes" apart, which is exactly the distinction a first-slip-vs-lockout call needs.
Past that point, accuracy barely moves, but the count of distinct contexts in use keeps climbing steadily. That's the tell. Once the window is longer than the system's real memory, a bigger k stops finding new structure and starts memorizing specific stretches of the one trace you happened to record — a bigger table, not a better model. The gap between "accuracy plateaus" and "context count keeps growing" is a working, computable stand-in for the true number of states, without ever being told what they were.
This is the same tension MIT's program synthesis course lays out for language models of code, just relabeled. An n-gram model of text is exactly a k-tails machine with the window fixed at n: cheap to fit, but blind to anything longer, the way a model reading one word of context can predict bear from "the big brown" but has no hope of predicting roar six words later. Recurrent networks and transformers exist specifically to remove that ceiling — instead of a hand-picked k and a table that grows with it, they learn a fixed-size context vector that compresses however much history turns out to matter. Point that machinery at a trace of system events instead of a corpus of source code, and "language model" and "induced state machine" become close to the same object: the model's hidden state at each step stands in for whichever node of the statechart the real system was in when it emitted that event.
The reason to bother is almost always one of three things: turning an undocumented legacy service's logs into a first-draft diagram a person can then correct by hand; flagging any transition the model never saw and therefore never learned to expect, which is often exactly where the interesting bugs or intrusions live; or predicting, given the history so far, what the system is likely to do next. Harel's statecharts made a known system's behavior small enough to draw. Model inference is the same problem run backward — recovering a drawable, checkable machine for a system whose only surviving description is what it happened to do.
Statecharts didn't stay a niche notation. Harel's original tool, Statemate, fed directly into UML's state diagrams and later into SCXML, and today the same hierarchy-plus-orthogonality shape shows up quietly in the state machine libraries behind embedded firmware, game AI, and workflow engines — most engineers using nested and parallel states have never read the 1987 paper, but they're using its vocabulary.
What's changed is the rest of the problem. Harel's contribution was almost entirely about representation: how do you keep a diagram of a genuinely complex reactive system small enough for a person to still read it. Tools like P pick up from there and ask the question a diagram alone can't answer — given that representation, is the system actually correct, across every order events could plausibly arrive in? And specification mining picks up a third thread — what do you do when nobody drew the diagram at all, and the only description of the system left is the trace of what it did? All three depend on the same compression Harel found first: you can't search a space of behaviors exhaustively, or learn one from data, until you have a formalism compact enough to describe that space in the first place.