[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:

  1. A regular expression
  2. A finite automaton (DFA or NFA — equivalent)
  3. 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.

OperationClosed?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:

  1. 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 than bs, 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

LanguageWhy not regular
must count unboundedly
Balanced parenthesesunbounded nesting depth
must remember an arbitrary string
, gaps grow without bound
Palindromesmust 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.


↑ Back to Theory of Computation