Graphs and State Machines for Agents, Part 2: Every Graph Is a State Machine

Part 1, “From Lines to Graphs,” ended on a claim that sounds like a metaphor and is not one: the work an agent does has a shape, and that shape is a graph. Nodes for the states the work can be in, edges for the moves between them. This part collects the debt. Because there is a name for a graph whose edges are labeled with the events that trigger them, and it is not “agent framework” or “orchestration DAG.” It is a finite state machine, and it was fully specified before the transistor was common.

Here is the shift, named plainly. The agent world thinks it is inventing abstractions. It is rediscovering one. First we wrote chains: prompt into prompt into prompt, a straight line. Then the line was not enough, so we wrapped it in a loop and called it an agent: think, act, observe, repeat until done. Then the loop sprawled into something with branches and retries and human checkpoints, and the loop stopped being a good description, so we reached for graphs. LangGraph models the work as a graph of nodes and edges. LlamaIndex Workflows models it as steps that emit and consume events. Chains, loops, graphs. Three names, one idea, and the idea is older than all of us.

“

Chains, loops, and graphs are the same object seen from three distances. That object is the finite state machine, and it already specifies TCP, regular expressions, and the control unit of your CPU.

”

The whole formalism fits in one sentence

Strip away the diagrams and a state machine answers exactly one question. Given the current state, when an event occurs, what is the next state? That is the entire idea. Everything else is bookkeeping around that one question.

Write it as a function and the shape is obvious:

transition(state, event) -> nextState

Read that signature slowly, because it is the load-bearing line of this whole series. It takes where you are and what just happened, and it returns where you go. Nothing about how the model feels, nothing about wall-clock time, nothing hidden. A pure lookup from a pair to a state.

The reason this matters is that your program already works this way. It just does not admit it. A React component holds state, receives an event (a click, a fetch resolving), and moves to a new state that re-renders. An HTTP request handler holds a connection’s state, receives bytes, and moves it forward. A game loop holds the world, receives a frame’s worth of input, and advances. An LLM agent holds a conversation and some scratch memory, receives a tool result or a user turn, and decides what happens next. Every one of these is transition(state, event) -> nextState wearing a different costume.

The only real decision you ever make is where that transition logic lives. And in almost every codebase, the honest answer is: nowhere in particular. It is smeared across a dozen event handlers, three useEffect blocks, a pile of if (isLoading && !isError) conditionals, and a retry wrapper somebody added under deadline. The machine exists. It always existed. It is just scattered across the file so thinly that no single person can see the whole thing, which is exactly why it breaks in ways nobody predicted.

Writing the transition as one explicit function is not adding structure. It is gathering structure that was already there and hiding in the gaps.

The five-tuple, and why finiteness is the superpower

The textbook definition looks intimidating and is not. A finite state machine is:

M = (S, Σ, δ, s0, F)

Read it as five nouns you already understand:

• S is the finite set of states. The named situations the system can be in. idle, loading, success, failure. Finite is the operative word, and the source of all the power below.
• Σ (sigma) is the input alphabet. The set of events the machine can receive. SUBMIT, RESOLVE, REJECT, CANCEL. Not data, not payloads. The kinds of thing that can happen.
• δ (delta) is the transition function. A map from a (state, event) pair to the next state: S × Σ → S. This is transition() from above, written formally. It is a table, not an algorithm.
• s0 is the initial state. Where the machine starts before anything happens. idle.
• F is the set of final states. The states that count as done. Terminal, accepting, whatever your domain calls “the work is over here.”

The word that does the heavy lifting is finite, and it pays off in δ being a table. Because S is finite and δ maps finite pairs, the entire behavior of the machine can be written out and checked exhaustively. You can enumerate every state, every event, and every resulting move, and ask hard questions with a definite answer. Is there a state with no way out? Can you reach a bad state from the start? Does event X do anything at all in state Y? These are decidable. You can literally check them all.

Arbitrary code cannot make that promise. A normal function has effectively unbounded state (any integer, any string, the whole heap) and control flow that depends on runtime values you do not have until it runs. You cannot enumerate its behavior because there is no finite list to enumerate. A state machine trades expressive power for something better: it becomes checkable.

A small fork worth knowing, because the agent frameworks quietly pick a side. If δ returns exactly one next state for each (state, event) pair, the machine is deterministic: a DFA. If it can return a set of possible next states, it is nondeterministic: an NFA. This is not hand-waving about randomness. It is precise. A regular expression engine compiles your pattern into an NFA (the natural, permissive form), then either simulates that NFA directly or converts it into an equivalent DFA for a faster, single-path match. Same expressive power, different execution. Hold that DFA-versus-NFA distinction, because when you wire nondeterminism into an agent’s transitions on purpose, it becomes the thing that lets one machine fan out into many. Part 5 cashes that in.

The problem it actually solves: impossible states cannot be built

Formalism is worthless until it kills a bug you have personally shipped. Here is the one it kills, and if you have written a UI you have written this exact bug.

You are fetching data. You reach for the obvious variables:

// The four-boolean mess. Every data-fetching component starts here.
let isLoading = false;
let isError   = false;
let isSuccess = false;
let data:  Response | null = null;
let error: Error    | null = null;

Four booleans and two nullable slots. It feels reasonable. It is a trap. Those flags describe 2^n combinations, and almost all of them are nonsense. isLoading and isError both true renders a spinner on top of an error. isSuccess true with data still null crashes on the first property access. isError true with stale data from a previous call shows old numbers under an error banner. Nobody wants these states. The type system permits every one of them, and under a real race condition (a second request landing while the first is still in flight) your code will construct them, because nothing stops it.

The fix is not more guards. More guards means more places to get the guard wrong. The fix is to make the illegal states impossible to write down:

// One value. The illegal combinations no longer have a name.
type State =
  | { status: 'idle' }
  | { status: 'loading' }
  | { status: 'success'; data: Response }
  | { status: 'failure'; error: Error };

Look at what just happened. There is no way to be loading and failure at once, because a value is one variant or another, never both. There is no success without data, because the type carries the data only in that variant. The compiler now refuses to let you reach for error in the success branch. Functional programmers have a name for this move: making illegal states unrepresentable. You did not add a rule that forbids the bad combination. You built a world where the bad combination has no name, so it cannot be spoken.

That single enum buys two guarantees that no amount of careful if writing ever gave you:

• The system is always in exactly one state. Not a fog of four booleans you have to read together and reason about. One value, one answer to “where are we.” You can print it, log it, put it on a dashboard, and it means one thing.
• Movement happens only along transitions you defined. The machine goes from state to state exclusively through δ. If you did not write a move, it does not exist, and the runtime will not invent one for you.

The double-click bug that stops existing

You see the payoff of “movement only along defined transitions” where a whole class of bugs evaporates.

A user submits a form. The request is in flight. Impatient, they click submit again. In the four-boolean world, that second click fires the handler, which starts a second request, and now you have a duplicate submission: two orders, two charges, two rows. The usual fix is a pile of defense: a disabled flag on the button, a debounce timer, an in-flight boolean you check at the top of the handler. Machinery to prevent a thing.

In the state machine, look at what the second click does. The machine is in loading. You go to δ and ask: in loading, what does SUBMIT do? You never defined a transition for SUBMIT in loading, because it is nonsense to submit while already submitting. So δ has no entry, and the event is ignored. Not blocked, not caught, not defended against. Ignored, because the move does not exist.

“

You did not fix the double-submission bug. You built a machine in which it was never expressible. The disabled flag, the debounce, the in-flight guard: all of it is scaffolding to simulate a property the state machine gives you for free.

”

This is the difference between defending against bad states and making them unrepresentable. Defense is a list of rules you have to remember to write, in every handler, forever, and the one you forget is the bug in production. Unrepresentability is structural: the bad thing has no name, so no code, present or future, careful or careless, can construct it.

Why now: the loop hit a wall the graph was built to climb

None of this is new mathematics. So why is the agent world reaching for it this year rather than five years ago? Because the loop finally hit the wall that state machines were invented to climb.

The frameworks are the tell. When LangGraph, LlamaIndex Workflows, and the dynamic-workflow patterns in coding agents all converge on “model the work as a graph of states and events” inside the same short window, that is not fashion. That is a field independently rediscovering that the abstraction they need already has a name, a formal definition, and seventy years of tooling behind it.

You can see the machine now

Go back to the handle this series turns on: a prompter asks a question; an architect draws a graph. Part 1 said the work has a shape. This part named the shape. The graph you draw is a finite state machine, the same object that specifies TCP and compiles your regular expressions, and drawing it is what makes your system checkable instead of hopeful. The whole discipline compresses to one instruction you can carry into any framework: name the states, the events, and the transitions.

That is the seeing. It is not yet the building. A real machine needs more than the five-tuple: it needs context (the data that rides along with the state), guards (conditions on a transition that decide whether it fires), and actions (the side effects that run as you move). Those three are what turn the diagram into something that runs, and they are also where statecharts extend the plain FSM into something that scales to real software. Part 3, “Building the Machine,” constructs one end to end.