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.