Regular expressions

The formula

The whole language is three operators over an alphabet:

R ::= ∅ | ε | a | R₁ R₂ | R₁|R₂ | R*

Reading: every regular expression is built from nothing, the empty string, and single characters, combined by exactly three operations — concatenation (this, then that), alternation (|, this or that), and the Kleene star (*, zero or more repeats). Character classes, +, ?, {m,n}, and anchors are all shorthand for combinations of these three.

The star, unpacked:

L* = {ε} ∪ L ∪ L·L ∪ L·L·L ∪ …

Reading: L* matches the empty string, one copy of L, two copies, three — any finite number of repeats, glued end to end. This one operator is where all the power and all the trouble lives.

Kleene's theorem, the result underneath every implementation:

regular expression  ⇔  finite automaton

Reading: any pattern you can write in the three-operator language, some finite state machine recognizes, and vice versa — a regex is a state machine you can type. Thompson's construction makes the machine mechanically, with at most two states per pattern symbol ^[6].

The cost of a match:

automaton simulation:   O(m·n)      (m = pattern size, n = text length)
backtracking engine:    O(2ⁿ) worst case

Reading: run the pattern as a state machine and matching time is proportional to pattern size times text length, guaranteed. Run it by trial-and-error backtracking — as Perl, PCRE, Python, and Java do — and a pathological pattern goes exponential ^[5].

Where you meet it

Post-run log triage at the test stand. The run produced two gigabytes of serial and DAQ log. grep -E 'FAULT|OVERTEMP|LIMIT[_ ]?EXCEED' run_0347.log is the first move, and the second is a tighter pattern with a timestamp anchor so you only see events inside the window when the anomaly happened. The engineer who can sharpen a pattern in three tries owns the debrief.
On the bench, pulling numbers out of instrument chatter. SCPI responses, GPS NMEA sentences, and telemetry frames are text with a shape. A capture group like VOLT ([0-9]+\.[0-9]+) turns a scroll of analyzer output into a column you can plot. Half of every quick-look script written in the cluster is regex feeding matplotlib.
In the data-reduction script the review board trusts. Somewhere in the pipeline is a validation pattern deciding which telemetry rows are well-formed enough to count. If that regex silently rejects a legitimate line format the vendor changed last month, the "clean" dataset at the TRR is quietly missing data — and nobody voted on that.
In production filters. Firewall rules, CI log scanners, alarm-suppression filters on ground software — regexes running unattended against input nobody screened. This is where the exponential failure mode stops being theoretical (see below).

How it works

A regular expression is a finite automaton in disguise: a machine with a fixed set of states and no other memory. The machine reads the text one character at a time, moves between states, and reports a match when it lands in an accepting state. That fixed memory is both the guarantee and the boundary. Guarantee: matching can be done in time proportional to text length, streaming, without ever backing up ^[5]^[6]. Boundary: a fixed number of states cannot count arbitrarily high, so no true regular expression can match balanced parentheses, nested brackets, or properly paired XML tags — the machine would need a new state for every nesting depth ^[1]. When you catch yourself writing a regex to parse a nested structure, stop; that job belongs to a real parser, and the regex that "mostly works" on nested input is a latent bug with your name on it.

Modern engines split into two families, and knowing which one you are holding matters. Automaton-family engines — grep, awk, RE2, Rust's regex — simulate the state machine directly and deliver the O(m·n) bound ^[5]. Backtracking engines — Perl, PCRE, Python's re, Java's java.util.regex — try alternatives recursively, which buys convenience features the automaton cannot support (backreferences like (\w+) \1, lookaround), at the price of exponential worst-case time ^[1]^[5]. Backreferences genuinely leave the regular languages; matching with them is NP-complete in general ^[1]. Russ Cox's standard benchmark: matching a?ⁿaⁿ against 29 a's takes a backtracking Perl over 60 seconds where the automaton takes about 20 microseconds ^[5].

The failure has a name — catastrophic backtracking — and a signature: nested or adjacent unbounded quantifiers, like (a+)+ or .*=.* inside a larger .* ^[1]^[13]. Verified on this machine: Python's re.match(r'(a+)+$', 'a'·26 + 'b') takes about 4 seconds, and every added a doubles it — 30 characters is a minute, 40 is a season. The input that triggers it is the near-miss: a string that almost matches, forcing the engine to try every way of splitting the repeats before giving up. On 2019-07-02 a firewall rule containing .*(?:.*=.*) did exactly this to Cloudflare, pinning CPUs worldwide and taking their network down for 27 minutes; the fix included moving to a linear-time engine ^[13]. The engineering rule that falls out: any regex that runs unattended against input you don't control either gets a linear-time engine, a timeout, or a rewrite without nested quantifiers.

Smaller gotchas that cost real bench time: quantifiers are greedy by default, so ".*" swallows from the first quote to the last quote on the line, not the nearest — ".*?" or "[^"]*" is what you meant. . typically does not match newline. Most library search calls match anywhere in the string unless you anchor with ^ and $, which is how a part-number validator accepts XX-1234-garbage. And the dialects disagree: POSIX BRE (default grep, sed) treats + and ? as literals unless escaped, while ERE (grep -E) and PCRE treat them as operators ^[12] — the pattern that works in Python and silently fails in sed is a rite of passage.

History

The theory came out of neurons, not text files. Warren McCulloch and Walter Pitts had modeled nerve nets as simple logical machines in 1943, and in the summer of 1951 Stephen Kleene — a logician from the University of Wisconsin, one of the founders of recursion theory — spent a stretch at the RAND Corporation working out exactly which patterns of events such a finite machine could recognize ^[2]^[3]. His answer was an algebra of "regular events" built from union, concatenation, and the iteration operator that now carries his name, and the theorem that this algebra captures precisely what finite automata can do. The RAND memorandum was published in 1956 as "Representation of Events in Nerve Nets and Finite Automata" in the Automata Studies volume ^[1]^[2].

The theory became a tool in 1968, when Ken Thompson at Bell Labs published "Regular Expression Search Algorithm" in the Communications of the ACM — a method that compiled a regex into a nondeterministic automaton and tracked all its states in parallel, never backtracking; his implementation generated IBM 7094 machine code on the fly inside the QED editor ^[1]^[4]^[5]. The notation moved into Thompson's ed editor on Unix, where g/re/p meant "globally find the regular expression and print." When Doug McIlroy asked for a standalone version of that command, Thompson famously produced it "overnight" — by his own account he mostly spent an hour debugging a private search tool he already had — and grep shipped with Version 4 Unix, whose manual is dated November 1973 ^[7]^[8].

From there it was standardization and spread: Henry Spencer posted the first freely available regex library to Usenet in January 1986, and early Perl adapted it ^[1]^[9]; POSIX.2 froze the BRE and ERE dialects as IEEE Std 1003.2-1992 ^[1]^[11]^[12]; and in 1997 Philip Hazel wrote PCRE — Perl-Compatible Regular Expressions — for the Exim mail server, the library that carried Perl's syntax into Apache, PHP, and nearly everything else ^[1]^[10]. Seventy-plus years on, the notation a logician invented to describe nerve nets is the first thing an engineer types after a failed test run.

Related tools

/tools/adc-resolution — the data words you end up regex-ing out of hex dumps and DAQ logs
/tools/snr-enob — the bench numbers your capture groups pull from analyzer output
/tools/loop-4-20ma — the process-instrumentation world whose Modbus logs get grepped at 2 a.m.

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →