Kleene's Theorem: Regex Equals Automata

Two languages for the same idea

In the first two guides of this rung you learned to write a regular expression from three operations — union, concatenation, and the Kleene star — and then to read off the exact set of strings it denotes. That gave you an algebraic, type-it-on-one-line way to specify a pattern, like (a|b)*abb for 'any string over {a, b} ending in abb.' Back on the earlier rungs you had a completely different way to specify a pattern: draw a finite automaton — a turnstile-like machine that remembers only its current state and follows arrows on each symbol.

These two descriptions feel utterly different. One is a string of symbols you type; the other is a diagram of bubbles and arrows you draw. So a natural worry arises: maybe regular expressions can express patterns that no automaton can recognize, or maybe automata can recognize patterns that no expression can capture. Kleene's theorem settles this worry decisively, and the answer is the cleanest possible: the two are exactly equivalent in reach.

What the theorem actually claims

Kleene's theorem says: a language can be described by some regular expression if and only if it can be recognized by some finite automaton. Combined with the result you already trust — that DFAs, NFAs, and epsilon-NFAs all recognize exactly the same class, the regular languages — you now get a single class of languages with three interchangeable names: 'describable by a regex,' 'recognized by a finite automaton,' and 'regular.' They are three windows onto one room.

An 'if and only if' is really two claims that must both be proved, and each direction is a concrete construction you can run by hand. Forward: given any regular expression, build a machine that recognizes its language — this is the Thompson construction, which assembles a small epsilon-NFA. Backward: given any finite automaton, extract a regular expression that denotes its language — this is state elimination, powered by an algebraic identity called Arden's rule. The next guide walks both procedures slowly with full examples; here we want you to genuinely understand why each works and what it buys you.

Forward direction: build a machine from the expression

The forward direction works by structural induction — exactly the proof shape the earlier rung taught you. A regular expression is built up from tiny base cases (the empty-language symbol, the symbol for epsilon, and a single letter from the alphabet Sigma) glued together by the three operations. The Thompson construction gives one matching machine for each base case, plus a way to wire two sub-machines together for each operation. If we can do all of those, then by induction every regex has a machine.

The magic ingredient that makes the wiring trivially clean is the free, input-consuming-nothing epsilon-transition you met one guide earlier. Each Thompson sub-machine is built with a strict discipline: exactly one start state and exactly one accept state, and no stray arrows into the start or out of the accept. That uniform shape is what lets you glue pieces together like LEGO bricks using epsilon-arrows, without the joints leaking unwanted strings.

BASE: for a single letter a, build start --a--> accept. For epsilon, build start --epsilon--> accept. For the empty language, build a start and a separate accept with NO arrow between them (nothing is accepted).
UNION (R|S): add a fresh start with epsilon-arrows into the starts of R's and S's machines, and a fresh accept with epsilon-arrows from both their accepts — clone yourself into either branch.
CONCATENATION (RS): glue them end to end — put an epsilon-arrow from R's accept to S's start, so a string must run through R and then S.
STAR (R*): add a fresh start that is also accepting (to allow zero copies = epsilon), with an epsilon-arrow into R's start, and an epsilon-arrow from R's accept back to R's start (to repeat) and forward to the new accept.

Backward direction: read an expression off a machine

The other direction is more surprising the first time you see it. Take any automaton, with its tangle of states and arrows, and squeeze it down — one state at a time — until only a start and a single accept remain, with one arrow between them labelled by the answer regex. This is state elimination. To make the labels behave during the squeeze, we first promote the machine to a generalized NFA, where an arrow may be labelled not just by a single symbol but by a whole regular expression.

When you delete an intermediate state q, you must preserve every path that used to travel through q. If an arrow comes into q labelled X, q has a self-loop labelled Y, and an arrow leaves q labelled Z, then deleting q replaces those by a direct arrow labelled X Y* Z — 'go in, loop on q any number of times, go out.' That Y* is the Kleene star earning its keep: the self-loop could be taken zero or more times, which is exactly what star means. You repeat this for every pair of neighbours of q, unioning with any arrow that already connected them.

Eliminating state q  (X = arrow in, Y = self-loop, Z = arrow out):

        X            Z
   p ------>  ( q )  ------> r        Y is q's self-loop
                ^_____|
                  Y

   after deleting q, the path p -> r is labelled:

        p --[ X Y* Z ]--> r        (union this with any old p->r label)

Why Y* ?  the loop on q may be used 0, 1, 2, ... times,
and "0 or more repetitions" is exactly the Kleene star.

The one rule of state elimination: a path through q becomes X Y* Z. The self-loop turning into a star is the whole trick.

Behind this picture is a clean algebraic fact, Arden's rule: if a set of strings X satisfies the equation X = A X | B (where A does not contain epsilon), then the unique solution is X = A* B. You can read a finite automaton as a system of such equations — one unknown per state, standing for 'the strings that lead from here to acceptance' — and Arden's rule lets you solve the recursive equation for a looping state by turning the loop into a star, mirroring the X Y* Z move exactly.

Why this bridge matters

Because the conversion runs both ways, you may design in whichever language is easier and translate when convenient. Proving a language is regular? Just write one regular expression for it — Kleene's theorem instantly guarantees a machine exists, no diagram needed. Want to prove some closure property of the regular languages, or to actually scan text in a compiler? Turn the regex into an automaton and run it. This two-way bridge is the engine under real tools: a regex engine in a text editor, or the scanner that a compiler's lexical analyzer uses, typically compiles your pattern into a finite automaton and then races a single pointer through your input.

But here is the honest caveat you must carry into the rest of your life as a programmer. The 'regular expressions' in many programming languages are NOT the mathematical object Kleene's theorem is about. They bolt on extra features — most importantly backreferences (matching the same text seen earlier, as in (.+)\1) and lookahead/lookbehind. A backreference can describe languages that are provably not regular, so no finite automaton recognizes them; the equivalence simply does not apply to those features.