Finite State Machines: The Simple Idea Behind Regex Engines and Traffic Lights
A traffic light never remembers how long it's been green -- it just knows which color it is right now, and that's the entire idea behind a finite state machine.
A traffic light is never doing math, tracking history, or remembering how long it's been green. At any given moment it's in exactly one condition -- red, yellow, or green -- and a fixed rule decides what happens next: green eventually goes to yellow, yellow always goes to red, red goes to green. That's the entire idea behind a finite state machine: a small, fixed set of states, one of them active at a time, and clear rules for what triggers a move from one state to the next.
Formally, a finite state machine has a set of possible states, one designated starting state, and a transition rule for every state that says, given some input, which state comes next. Crucially, the machine doesn't need to remember anything about how it got to its current state -- the traffic light doesn't care whether it's been a slow Tuesday or a busy Friday, only that it's currently green and a timer (its "input") just fired.
Regex engines are finite state machines wearing a disguise. When a regular-expression pattern gets compiled, the engine builds a machine where reading each character of the input text is an input that moves the machine along a transition -- from one state to the next -- and a match happens if the engine lands on a designated "accepting" state by the time it finishes reading. A pattern like ab* compiles into states for "seen nothing yet," "seen an a," and "seen an a followed by any number of b's," with transitions wired up exactly like a traffic light's red-yellow-green cycle, just with more than three states.
The same shape turns up everywhere state matters more than history: a turnstile is a two-state machine (locked, unlocked) that flips on a coin input; a TCP connection walks through a well-defined sequence of states like SYN_SENT and ESTABLISHED; a parser tracks whether it's currently inside a string literal, a comment, or plain code, one state at a time.
The limitation is just as instructive as the idea itself: a finite state machine can't count arbitrarily high or remember arbitrarily far back, because doing that would require more than a fixed handful of states -- it would require actual memory, like a stack. For validating a pattern or tracking a fixed set of conditions, though, a traffic light's worth of state is often exactly enough.