From a Graph to a State Machine

Almost everyone has implemented a state machine without calling it that. The lifecycle of an order, of a download, of a connection. It’s often modeled with a handful of loose booleans that, three months later, nobody can read. That’s exactly what state machines are for.

Before getting there, it’s worth building the concept from the bottom up. And at the very bottom there’s a graph.

01 — The graph

An automaton is a graph with rules on top, so we have to start with the graph.

A graph is the simplest structure for representing relationships. Two sets: nodes (the elements) and edges (the connections between them).

Metro stations are a graph: each station is a node, each stretch of track joining two stations is an edge. A network of friends is one too: people are nodes, friendships are edges.

Formally it’s written G = (V, E): V is the set of vertices (nodes) and E the set of edges. You don’t need more to get started.

02 — The directed graph

In the metro graph, an edge has no direction. If the line joins Sol with Gran Vía, it joins Gran Vía with Sol. The connection is symmetric.

In a directed graph (or digraph) the edges have direction. The edge goes from A to B, and that doesn’t imply one exists from B to A.

Following someone on a social network is a directed graph: one account following another doesn’t mean the other follows back. A one-way street, same thing.

That asymmetry is what lets you model “from here you can go there, but not the other way around.”

03 — The automaton: a graph with rules

A finite automaton is a directed graph with four rules added on top:

• The nodes stop being “elements” and become states.
• The edges stop being loose connections and become transitions, each one labeled with the event that triggers it.
• One state is the initial one: where you start.
• One or more are final or accepting states.

A traffic light is a finite automaton we all carry in our heads. Three states: Green, Amber, and Red. The event that triggers the change is the passing of time, and the transitions go in a single direction: Green → Amber → Red → Green, and round again. You don’t jump from Green to Red: that edge doesn’t exist in the graph, and that’s why it doesn’t happen. The Amber is there precisely to make that jump impossible.

Formally a finite automaton is defined as (Q, Σ, δ, q0, F): the set of states, the alphabet of possible events, the transition function, the initial state, and the final ones. Out of all that notation, one idea is worth keeping: a finite automaton has no more memory than the state it’s in. All it “knows” is where it is right now.

04 — The finite limit

That limit (having no more memory than the current state) is what separates the finite from the infinite. The set of states is finite. When you need to remember an amount of information that isn’t bounded, a finite number of states isn’t enough, and you have to level up: a pushdown automaton adds a stack as memory, and a Turing machine adds an infinite tape. The infinite is never in the drawing of the graph — it’s in the memory.

In programming you almost never want to get there. If the number of states starts growing out of control or depends on the data, that’s a bad sign: the model is off, and adding states only hides it.

A number of states that explodes is usually a symptom that there’s a variable disguised as a state.

05 — The state machine

A finite state machine (FSM) is that directed graph taken into code: a finite number of states, the system is in exactly one at a time, and it moves to another only when an event that draws that transition occurs. Nothing else can happen.

The canonical example is a download manager:

State machine · download manager

initial stateterminal state

• Pending: the download exists but hasn’t started.
• Downloading: in progress. It can be paused or cancelled.
• Paused: halted. Resuming it goes back to Downloading (that return is a cycle, and it’s perfectly legal) or it can be cancelled.
• Completed, Failed, and Cancelled: terminal states, with no outgoing edges. This is the end of the line, not quite the “final” states of an automaton (which can still have transitions).

Failed and Cancelled end the flow the same way, but they’re not the same state. One is caused by the system; the other is decided by the user. Merging them into a single terminal state would save one state and lose exactly the piece of information that matters when things leave the happy path.

What’s interesting isn’t what’s allowed, but what’s forbidden by construction. You can’t pause something that’s Pending: it hasn’t started yet. A Paused download can’t fail: it isn’t transferring anything, it would first have to go back to Downloading. You can’t cancel a download that’s already Completed. Those transitions don’t exist in the graph, so they shouldn’t exist in the code either.

06 — The trade-off

Modeling a flow as a state machine is a trade-off: it adds structure, and structure has a cost. It’s worth looking at both sides.

What you gain. Against a handful of booleans, an FSM brings four things:

• Clarity. The control flow is explicit. One state at a time. The if (isPending && !isFailed && !isCompleted && isPaused) that nobody dares to touch simply disappears.
• Extensibility. Adding a new state is adding a node and its edges. If the machine is well encapsulated, you don’t touch the logic that already works.
• Testing. Each transition is a unit. You test “from Paused, the resume event leads to Downloading” on one side, and “from Completed, the resume event does nothing” on the other. State by state, transition by transition.
• Maintenance. When the state is explicit, a bug like “the download got stuck halfway in some weird limbo” stops being possible: either you’re in a valid state, or the transition failed in a controlled way.

An FSM doesn’t simplify the problem: it makes it explicit. And an explicit problem is one you can test, extend, and debug.

What it costs, and when it isn’t worth it. Not every flow deserves that structure. If the process is trivially linear — A → B → C, no branches, no cycles, no invalid transition that’s dangerous to let through — building a state machine is over-engineering. A couple of fields and a method are enough.

The FSM is worth it when there are transitions that must be impossible, when the same state is read and mutated from several places, or when the booleans start multiplying and contradicting each other: isPaused set to true with isCompleted also true is a state that shouldn’t exist, and one that a single explicit state can’t even represent.

By the way: this is the same machine that showed up in the Kafka post, when we said the producer has to validate a booking’s lifecycle before emitting events. With different node names, it’s the same drawing.