Regular Languages & Regex
The regex you use every day is finite automata in disguise — and knowing that explains its powers and its limits.
Three Names for One Thing
A regular language can be described three equivalent ways — Kleene’s theorem says they define exactly the same set of languages:
| Description | Form | Example |
|---|---|---|
| Finite automaton | States + transitions | The even-1s DFA |
| Regular expression | Pattern algebra | (0|1)*1 — ends in 1 |
| Regular grammar | Rules like A → aB | S → 0S | 1S | 1 |
The Three Operations That Build Everything
Every regular expression is built from three operations over an alphabet — everything else (+, ?, character classes) is shorthand:
| Operation | Regex | Means |
|---|---|---|
| Union | a|b | a or b |
| Concatenation | ab | a then b |
| Kleene star | a* | zero or more a’s |
# email-ish: word chars, @, domain, dot, tld ^[\w.]+@[\w]+\.[a-z]+$ # these desugar to union/concat/star underneath: a+ = aa* # one or more a? = (a|ε) # optional [0-9] = (0|1|...|9) # character class = big union
When you write a+, the engine builds the same NFA as aa*. Understanding the desugaring is how you reason about what a pattern can and can’t match.
The Limit — and the "Regex" That Cheats
Regular languages can’t count unbounded nesting. You cannot match balanced parentheses with a true regex — that needs a stack (a context-free grammar, the next guide). The famous “don’t parse HTML with regex” rant is this exact theorem: nested tags aren’t regular.
\1) and recursion — features that make them more than regular (and can blow up to exponential time: “catastrophic backtracking”). Pure regular expressions match in guaranteed linear time; those extensions are why some “regex” hangs your server.Closure — Why Regex Composes So Well
Regular languages are closed under union, concatenation, star, intersection, and complement — combine two regular languages with any of these and the result is still regular. That’s why regex features compose cleanly and why tools like grep can AND/OR patterns without ever leaving linear-time territory.
Interview Questions
What are the three equivalent definitions of a regular language?
A finite automaton (DFA/NFA), a regular expression, and a regular grammar — Kleene’s theorem proves they describe exactly the same class of languages.
Why does regex run in linear time (in the pure form)?
The pattern compiles to an NFA/DFA, which reads the input once, one symbol per step, with no backtracking. Time is O(n) in the text length — provided no backreferences.
Can regex match balanced parentheses? Why or why not?
Not with a true regular expression — balanced nesting requires counting depth, which needs a stack. That’s a context-free language, one class up. Engines that appear to do it use non-regular recursion extensions.
What is catastrophic backtracking?
With backreferences/nested quantifiers, a regex engine can explore exponentially many match paths on certain inputs (e.g. (a+)+$ against a long non-matching string), hanging for seconds — a real DoS vector (ReDoS).