[Intermediate] — What finite memory can and cannot recognise, and how to prove a language is out of reach.
Three equivalent definitions
A language is regular if it’s described by any of:
- A regular expression
- A finite automaton (DFA or NFA — equivalent)
- A regular grammar (all productions or )
Kleene’s theorem says these coincide exactly. Which definition you use is a matter of convenience.
The regular operations — and regular languages are precisely what you get by closing single symbols, , under them:
Closure properties
Regular languages are closed under almost everything, which is unusually convenient and is why regular tools compose so well.
| Operation | Closed? | How |
|---|---|---|
| Union, concatenation, star | ✓ | by definition |
| Complement | ✓ | swap accepting and non-accepting states of a DFA |
| Intersection | ✓ | product construction, or De Morgan on complement+union |
| Difference | ✓ | |
| Reversal, homomorphism | ✓ |
Complement is the striking one, and it’s why the DFA/NFA distinction matters. Flipping the accepting states of a DFA gives exactly the complement. Doing that to an NFA does not work — an NFA accepts if some path accepts, so flipping gives “some path rejects”, which isn’t the complement. You must determinise first.
The product construction for intersection: run both DFAs simultaneously, with states , accepting when both accept. Simple, and it’s how tools combine multiple patterns.
Why closure properties are useful: they let you prove non-regularity indirectly. If were regular, then would be regular — and if you can show that intersection is a known-irregular language, you’re done. Often much easier than a direct pumping argument.
The pumping lemma
The standard tool for proving a language is not regular.
If is regular, there’s a pumping length such that every string with can be split where:
- for every
Where it comes from, which is more useful than memorising it: a DFA with states reading a string of length must revisit a state — pigeonhole. The substring consumed between the two visits is a loop, and a loop can be traversed any number of times. So the pumped strings must also be accepted. → Pigeonhole
Using it
It’s an adversary game, and the quantifier order is what people get wrong:
- The adversary picks (you don’t know it)
- You pick with — choose wisely
- The adversary picks the split (you must handle all valid splits)
- You pick to force a contradiction
Claim: is not regular.
Proof. Suppose it is, with pumping length . Take .
Since , consists only of s — that’s what condition 2 buys you, and it’s why the condition exists.
Pump with : has more
as thanbs, so it’s not in . Contradiction.
Choosing well is the skill. A bad choice lets the adversary pick a that pumps harmlessly. works because condition 2 traps inside the as.
Two warnings:
It’s necessary, not sufficient. Passing the pumping lemma does not prove regularity — there are non-regular languages that pump. For a proof of regularity, build an automaton or use Myhill–Nerode.
Get the quantifiers right. You don’t get to choose the split; the adversary does. Handling only one convenient split is the commonest error in a pumping proof. → Quantifier order
Myhill–Nerode
The complete characterisation, and unlike the pumping lemma it works in both directions.
Define if no suffix distinguishes them: for every , .
is regular if and only if has finitely many equivalence classes.
And the number of classes is exactly the number of states in the minimal DFA.
The intuition: a state is precisely “everything the machine needs to remember”, and two strings need the same state exactly when no future input can tell them apart. Finitely many things to remember ⟺ finite automaton. → Equivalence relations
Applied to : are pairwise distinguishable — but for . Infinitely many classes, so not regular. Cleaner than the pumping argument, and it also tells you the minimal machine.
Non-regular languages worth recognising
| Language | Why not regular |
|---|---|
| must count unboundedly | |
| Balanced parentheses | unbounded nesting depth |
| must remember an arbitrary string | |
| , | gaps grow without bound |
| Palindromes | must compare front to back |
The common thread: they all require unbounded memory. Finite state gives you a bounded amount of “what have I seen”, and any language needing more is out.
Contrast with what is regular and looks harder than it is:
- Strings with an even number of
as — one bit of state - Strings whose value mod 7 is 0 — seven states, and this is genuinely surprising the first time
- Any finite language — trivially, just enumerate it
- Nesting bounded to depth 3 — regular, with many states
“Bounded” is the word that decides it. Nesting to depth 3 is regular; arbitrary nesting is not.
The practical payoff
This note’s whole value is knowing when a regex is the wrong tool — and being able to say why rather than just that.
A regex cannot parse:
- HTML/XML — arbitrary nesting. The famous Stack Overflow answer is correct, and this is the theorem behind it
- JSON — nested objects and arrays
- Source code — nested blocks, balanced brackets
- Any recursive structure
A regex is exactly right for:
- Tokenising — identifiers, numbers, string literals. This is what lexers are → Lexical Analysis
- Validating flat formats — dates, postcodes, simple patterns
- Search and replace on unstructured text
- Log filtering
The rule: if the structure can nest arbitrarily, you need at least a stack, which means a parser. → Context-Free Languages
And the corollary people miss: reaching for a regex on nested input doesn’t produce a slightly-wrong solution that you can patch. It produces one that is wrong on inputs you haven’t imagined, permanently. The right move is to switch tools, not to add another special case to the pattern.
Email validation is the recurring cautionary tale. RFC 5322 permits nested comments, so a fully-correct email regex does not exist. The practical answer — used by every serious system — is a loose sanity check plus sending a confirmation link. The theory tells you to stop trying.
Practical notes
Regular languages are cheap. DFA matching is in input length with memory — one pass, one integer of state. Nothing beats that, which is why lexers are fast and why finite automata are used in hardware and hot paths.
Know your engine. POSIX/RE2/Rust are true regular engines with linear guarantees. PCRE/Perl/Python/Java add backreferences, exceeding regular and risking exponential time. → Catastrophic backtracking
Compile once, match many. Building the automaton is the expensive part.
Ask “does this nest?” first. It’s the one question that decides regex versus parser, and it takes five seconds.
Related
- Finite Automata — the machines
- Context-Free Languages — what you need when this isn’t enough
- Lexical Analysis — regular languages, industrially
- Theory of computation map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering