--- title: "State Machines" description: "States, events, and transitions — the groundwork for TCP, OS, and parsers." source: https://vizlearn.app/foundations/abstraction/state-machines --- # State Machines State machines are models that remember one current state, read one event, and use a transition rule to choose the next state and action. The key is the pair: `(state, event)`. An event by itself is not enough, which is why the same `push` can mean "reject" or "pass". Think of a turnstile with a tiny clipboard. The clipboard does not say "when push happens, do X." It says "when locked and push happens, reject" and "when unlocked and push happens, pass." Half the rule is the event. The other half is memory. ## How State Machines Work A deterministic finite-state machine has four working parts: - a finite set of states, here `locked` and `unlocked`; - a finite set of input events, here `coin` and `push`; - a transition table keyed by `(state, event)`; - a start state, here `locked`. On every event, the machine builds a key from the current state and the current event. It looks up that key in the table. If the row exists, the row tells it two things: the `next_state` and the `action` to emit. Then it assigns `state = next_state` and moves to the next event. The edge labels in the graph use the same order as the table output: `event / action`. For example, `coin / unlock` means the event is `coin` and the emitted action is `unlock`. That assignment is the whole engine. Nothing mystical hides between the graph and the table. The graph is the picture; the table is the executable contract. If they disagree, the table wins. Self-loops are real transitions, not "nothing happened." In the turnstile, `locked + push` keeps the machine locked and emits `reject`. `unlocked + coin` keeps it unlocked and emits `thank`. The state did not change, but the machine still consumed an event and emitted an action. ## State Machines Step by Step The default event tape is `push, coin, push, coin, coin, push`, and the machine starts in `locked`. 1. **Start in `locked`.** The table has four legal rows: both events under both states. 2. **Read `push`.** The current key is `(locked, push)`. That row says next state is `locked`, action is `reject`. This is a self-loop: the turnstile refuses the push and stays locked. 3. **Read `coin`.** The current key is `(locked, coin)`. That row says next state is `unlocked`, action is `unlock`. The state now changes. 4. **Read `push` again.** This is the same event as step 2, but not the same key. The key is now `(unlocked, push)`, so the row says next state is `locked`, action is `pass`. 5. **Read `coin`.** Back in `locked`, the key `(locked, coin)` unlocks the turnstile again. 6. **Read `coin` again.** Now the key is `(unlocked, coin)`. The row says stay `unlocked`, action is `thank`. A second coin does not lock the gate; it is a self-loop with a different action. 7. **Read the final `push`.** The key `(unlocked, push)` passes the person through and returns the machine to `locked`. The completed ledger is the proof: `push` appears with two different meanings, and `coin` appears with two different meanings. The event did not decide the behavior. The pair `(state, event)` did. Switch to `missing-rule` after the default run. It first reads a valid `coin`, moves from `locked` to `unlocked`, and then reads `timeout`. There is no row for `(unlocked, timeout)`, so the machine stops exactly there. A deterministic machine does not improvise. ## Why the Current State Matters If you throw away state and key the table by event alone, the turnstile becomes ambiguous. What does `push` mean? In `locked`, it means `reject`. In `unlocked`, it means `pass`. Both are correct in context; neither is correct without context. That is why state machines show up everywhere systems need disciplined memory. A TCP endpoint treats a segment differently in `LISTEN`, `SYN-SENT`, and `ESTABLISHED`. A parser treats the same character differently inside a number, inside a string, or after a delimiter. A UI button treats a click differently while `idle`, `loading`, or `disabled`. The machine is small because the lesson is about the shape of the idea. Big systems add more states, events, guards, and data, but the central lookup stays recognizable: current state plus input determines the next move. ## Edge Cases - **Empty event tape.** With no events, the machine stays in its start state, `locked`. No row is looked up. - **Repeated event, same state.** `push, push` while locked emits `reject` twice and stays locked twice. - **Repeated event, different state.** `push` after a coin is not the same as `push` before a coin; the state changed the key. - **Unknown event.** `timeout` has no row in the turnstile table. The trace stops on a missing transition instead of inventing behavior. - **Self-loop.** A row whose next state equals the current state still matters because it consumes the event and emits an action. ## Common Mistakes - Treating the event as the whole input. The input to the transition function is `(state, event)`, not just `event`. - Reading self-loops as no-ops. A self-loop can still reject, thank, log, retry, or fire an alarm. - Drawing a graph without a table. The graph is readable, but the table is what makes the behavior precise. - Adding a default fallback without naming it. If every missing row silently means "stay put," that is another transition rule. Write it down. - Forgetting the start state. The same event tape can produce a different trace if the machine starts somewhere else. ## A Note on Simplification This lesson shows a deterministic finite-state machine: one current state, one event at a time, one table row per legal transition. Real systems often add timers, concurrent actors, guard conditions, retries, and data carried along with a transition. Those details matter, but they sit on top of the first contract: the machine must know what state it is in before an event has a meaning.