Regex: Tiny Pattern, Hidden Machine

https://www.youtube.com/watch?v=4xhxORnBeo4 title: "Regex: Tiny Pattern, Hidden Machine" published: true tags: regex, computerscience, programming, beginners You type a regex and it matches text. But under the hood, your regex engine is building and executing a full state machine — every single time. From Pattern to Machine A regex like a(b|c)*d looks simple. Five characters. But when the engine compiles it, here's what actually happens: Each character becomes two states connected by a transition Concatenation chains state machines together Alternation ( | ) creates branching paths with epsilon transitions — free jumps that consume no input The star operator adds a loop from the accept state back to the start This is Thompson's construction , invented in 1968. Your tiny pattern becomes a nondeterministic finite automaton (NFA) — a graph with multiple possible paths at every step. NFA → DFA: Removing the Guesswork An NFA can be in multiple states at once. That's powerful but expensive t