Regular expressions have deep roots in formal language theory, a branch of theoretical computer science developed in the 1950s. The mathematical concept of "regular sets" was introduced by Stephen Cole Kleene in 1951, who described a notation (now called Kleene algebra) for representing patterns in formal languages. Ken Thompson implemented the first computational regular expression engine in 1968 for the QED text editor, and later incorporated it into the ed editor on Unix — the "g/re/p" command (global regular expression print) in ed became the standalone grep utility, embedding regex into the DNA of Unix computing.

At their theoretical foundation, regular expressions describe regular languages — the simplest class in the Chomsky hierarchy of formal languages. A regular language is any language recognizable by a finite automaton, a mathematical model of computation with a finite number of states. There are two types of finite automata: Deterministic Finite Automata (DFA), which have exactly one transition for each state-input pair, and Nondeterministic Finite Automata (NFA), which can have multiple possible transitions. Thompson's construction algorithm converts a regular expression into an NFA, and the subset construction algorithm can then convert that NFA into a DFA.

Modern regex engines use two fundamentally different approaches. NFA-based engines (used by Perl, Python, Java, JavaScript, .NET, and most languages) use backtracking: they try one path through the pattern, and if it fails, they back up and try alternative paths. This approach supports powerful features like backreferences (\1), lookahead (?=...), and lookbehind (?<=...) that go beyond theoretical regular languages. However, backtracking has a critical weakness: certain patterns against certain inputs cause exponential time complexity, known as "catastrophic backtracking" or ReDoS (Regular expression Denial of Service). The classic example is the pattern (a+)+$ matched against "aaaaaaaaaaab" — the engine explores 2^n paths before determining no match exists.

DFA-based engines (used by grep, awk, and Google's RE2 library) compile the pattern into a DFA that processes input in guaranteed linear time — O(n) regardless of pattern complexity. The tradeoff is that DFA engines cannot support backreferences or lookaround assertions, since these features require memory of previous match states that a true DFA cannot maintain. RE2, developed by Russ Cox at Google, was created specifically to prevent ReDoS attacks in web applications that accept user-provided patterns.

The regex syntax familiar to most programmers — character classes [a-z], quantifiers *, +, ?, alternation |, grouping () — has evolved significantly from Kleene's original notation. POSIX defined two standards (Basic Regular Expressions and Extended Regular Expressions), Perl added lookahead/lookbehind, non-greedy quantifiers, named groups, and Unicode properties, and these Perl-Compatible Regular Expressions (PCRE) became the de facto standard implemented by most modern languages. Understanding whether your engine is NFA or DFA-based, and whether your patterns risk catastrophic backtracking, is essential knowledge for writing robust regular expressions in production systems.