Regular Expressions Stopped Being Regular in 1994. Nobody Changed the Name.

A regular expression is a sequence of characters that defines a search pattern. That is the standard definition. It is also, in a meaningful sense, wrong -- or at least misleading about what most developers are actually working with when they write a regex today.

The story of how regular expressions went from a pure mathematics paper in 1956 to a slightly cursed feature of every programming language is one of the more interesting trajectories in computing. It is a story about how formal theory meets engineering pragmatism, how tools acquire features their inventors never intended, and why something developed to model how neurons fire ended up being used to validate email addresses.

Stephen Kleene did not invent regular expressions to search text. He was a mathematician at the University of Wisconsin working on formal language theory, and in 1956 he published a paper in a volume called Automata Studies that introduced what he called regular sets -- a notation for describing the sets of strings that finite automata could recognize. This work built directly on a 1943 paper by Warren McCulloch and Walter Pitts that modeled how neurons in the nervous system could be described mathematically. Kleene was trying to characterize what kinds of languages simple computational models could and couldn't process. The practical application he had in mind was nothing like grep.

The translation from theoretical notation to working software happened in the late 1960s, primarily through the work of Ken Thompson. Thompson was building text editors at Bell Labs, first QED and then ed, and he needed a way to let users search for patterns rather than literal strings. In 1968, he published a paper in Communications of the ACM titled Regular Expression Search Algorithm describing how to compile a regular expression into a program that could match it efficiently. He had applied for a patent on this mechanism a year earlier, in 1967, which was granted in 1971.

Thompson's ed editor allowed a command like g/pattern/p -- globally search for the regular expression and print matching lines. This command was so useful that Thompson extracted it into a standalone program. The name of that program was constructed directly from the command: grep. G for global, re for regular expression, p for print. Every time a developer types grep into a terminal, they are invoking a command whose name is an abbreviation of a line-editor command from the late 1960s. The software archaeology is unusually transparent.

What Kleene formalized and Thompson implemented were true regular expressions: patterns that could be matched by finite automata, meaning computations that have a fixed, finite amount of memory. The formal theory has a clean property: the time required to match a regular expression against a string of length n is always proportional to n, and only n. Linear time. This guarantee comes from the finite automaton at the core of a proper implementation.

Here is where the story gets complicated. Perl, which became the dominant text-processing language of the 1990s largely because of its pattern-matching capabilities, added features to regular expressions that are not regular in the formal sense. Backreferences -- the ability to refer back to text captured earlier in the same match -- require something more powerful than a finite automaton. They require memory that can grow proportionally with the input, which makes certain patterns susceptible to catastrophic backtracking: an exponential blowup in matching time on particular inputs. The security community knows this failure mode well. A deliberately crafted input can cause a poorly written regex to consume an unbounded amount of CPU time trying to determine whether the string matches. This class of vulnerability has a name: ReDoS, for Regular Expression Denial of Service.

The features Perl added were useful enough that every major programming language adopted them. JavaScript, Python, Java, Ruby, PHP -- all implement what is now called PCRE, Perl-Compatible Regular Expressions. The formal name regular expression persisted even as the thing being named acquired capabilities that put it outside Kleene's original definition. When a developer today says they are using a regular expression to parse a log file, they are often using a PCRE pattern that includes backreferences, lookahead assertions, non-greedy quantifiers, and named capture groups. Kleene would not recognize this as a regular set in the mathematical sense. It is more accurate to call it a pattern matching language that evolved out of regular expressions, inheriting the name and some of the syntax while quietly exceeding the original scope.

This is not a criticism. The extensions are genuinely powerful. Lookahead allows matching based on context that comes after the pattern without consuming it, enabling a class of constraint that would otherwise require multiple separate passes through the text. Named capture groups make complex patterns legible to readers other than the person who wrote them. The development of PCRE from Kleene's formal notation to a full pattern language happened because the theory, while clean, was insufficient for the problems real software needed to solve.

The gap between the formal definition and the practical tool explains why testing regexes interactively is so important. A pattern that looks correct on one input may backtrack catastrophically on another. A quantifier combination that seems obvious to the author may be ambiguous to the engine in a way that produces surprising matches. The same pattern that works in JavaScript may behave differently in Python if the two engines implement PCRE extensions differently. None of this can be reliably predicted by reading the pattern. It has to be tested against real examples, with edge cases, with inputs designed to expose backtracking.

The mathematician who published the 1956 paper was working at a level of abstraction where these concerns do not exist. Kleene's regular sets either match or they do not, in linear time, always. That is the price of the formal guarantee: expressive power limited to what finite automata can compute. Thompson made them useful by embedding them in an editor. Perl made them expressive by removing the formal constraint. The rest of computing inherited the result and now calls it regex.

When you write a pattern and run it against a test string, you are participating in a 70-year conversation between formal language theory and practical engineering. The name on the door still says regular expressions. The thing inside has traveled considerably further.