Regex Formalism

The Kleene star means zero or more repetitions of the subexpression it follows, joined end to end. Zero is the trap: a starred part can match the empty string, so on its own it never forces that text to be present.

A live state set records where the pattern is, not what the text matched. A backreference demands that an arbitrarily long captured substring occur again, and no fixed set of machine states can carry that text forward.

A backtracking engine explores one alternative at a time and rewinds the input when a branch fails. A state-set engine advances every live alternative together, consuming each input character exactly once.

Searching asks whether a match exists anywhere in the subject, not whether the whole subject matches. Without a start and end anchor, a pattern for four digits happily matches the four digits buried inside a longer string.

Concatenation, alternation and the Kleene star. Repetition binds tightest, then concatenation, then alternation, so ab*|c reads as (a(b*))|c. Parentheses exist only to override that order.

Ambiguity: a quantifier nested inside another quantifier, or alternation branches that can match the same text. A backtracking matcher then has exponentially many ways to split one input, and on a failing input it tries them all.

Groups are numbered by the left-to-right order of their opening parentheses, so an outer group always has a lower number than the groups nested inside it. Group 0 is the whole match, and non-capturing groups take no number.

All three are shorthand over the three operators. A class is an alternation of its members, R? is R or the empty text, R+ is RR*, and R{2,4} is RR(R(R)?)?. None of them lets a pattern describe anything new.

A backtracking matcher stops at the first path that succeeds, so only failure forces it to eliminate every alternative. An input that satisfies the ambiguous part for a long prefix and then defeats the rest maximises the number of paths to eliminate.

A lazy DFA cache stores subset-construction results computed on demand: each distinct set of live states becomes one deterministic state with its transitions. At the cap the engine flushes and rebuilds, or falls back to simulating the state set directly.

Two different match-selection rules are in play. Leftmost-first returns the first match the pattern's own preference order reaches, so branch order decides; POSIX leftmost-longest returns the longest match available at that position, whatever the order.

Kleene's theorem says patterns and finite automata describe exactly the same languages, in both directions: every pattern built from concatenation, alternation and the star has an equivalent finite automaton, and every finite automaton has an equivalent pattern.

Remove the ambiguity so every accepted string has exactly one way to match: flatten a quantifier nested in a quantifier, make alternation branches disjoint, and express a separated list as item followed by repeated separator-item. Then anchor, cap the input and prove it with a growth test.

Choose by who authors the patterns and what the budget must guarantee. Untrusted or frequently changed patterns on a hot path argue for a one-pass engine with a worst-case bound; a small reviewed set needing richer features can justify backtracking.

Treat a supplied pattern as untrusted code. Restrict what authors may express, screen patterns at admission for ambiguous shapes, cap input length, run each match under a budget, and isolate execution so a stuck match consumes one bounded, abandonable slot rather than a request worker.

An unanchored search whose pattern starts with a quantifier: the matcher retries the whole attempt at every starting offset, and each attempt can scan most of the input. That gives about n(n+1)/2 steps, quadratic rather than exponential.

Combine the patterns into one machine by alternation and tag every accepting state with the pattern it came from. One scan then advances the combined state set per character and reports each pattern whose accepting state is reached.

A global scan continues from the end of the previous match. A zero-width match ends where it began, so the next attempt starts at the same position and succeeds again, forever — unless the engine forces the position forward by one.

A backreference demands that a later span reproduce text captured earlier, which the three operators cannot express. Patterns using one can describe non-regular languages, so no equivalent finite automaton exists and Kleene's theorem stops applying.