Regular expressions
A regular expression is usually taught as a string of punctuation and explained with a warning: avoid nested quantifiers, or your program might hang. Both halves of that have a picture. Compiled to an automaton — the way production engines that promise linear-time matching actually work — a pattern is a handful of states and arrows, and matching is reading the input once while every possible position is tracked at the same time. Left as a naive recursive matcher instead, the "might hang" is not a warning to take on faith: it is a number, the count of attempts a failed match had to try before giving up, and it is drawn here as a tree rather than described as a risk.
- Thompson's construction (NFA)Compiles the pattern into a nondeterministic finite automaton and simulates every reachable state at once, so the whole input is read exactly once regardless of the pattern.O(n · m)O(m) space
- Subset construction (DFA)Pre-computes every reachable set of NFA states as a single DFA state, so matching needs to track only one active state at a time instead of a set.O(n)O(2^m) states, in the worst case space
- Naive backtrackingTries the pattern against the text recursively, choosing greedily and backtracking on failure — the simplest correct way to implement matching, and the one with no bound on how many attempts a failure can cost.O(n · m)O(n + m) stack depth space
Pattern matching over plain text, without an automaton at all, lives in String matching. Finite-state machines in a different setting are in the ReAct loop.