Thompson's Construction: Regex to State Machine
Every regular expression can be mechanically converted into an equivalent Nondeterministic Finite Automaton (NFA) — this is exactly how regex engines work under the hood, even though most programmers never see the intermediate automaton. Thompson's construction builds this NFA recursively: each basic regex operator (concatenation, alternation via |, and the Kleene star *) has a small, fixed NFA fragment pattern, and complex expressions combine these fragments using epsilon transitions (moves that consume no input) to wire them together.
The resulting NFA is often larger and more redundant than a hand-designed automaton for the same language would be, but the mechanical, rule-based construction process is exactly its advantage — it's guaranteed correct for any valid regex, which is why it's the standard textbook (and practical) approach rather than trying to design an equivalent automaton by intuition.
This is typically the first of a two-step pipeline: converting the regex to an NFA via Thompson's construction, then converting that NFA to a DFA via subset construction (see the NFA to DFA Converter) for actual efficient execution.