Two directions, one theorem
In the previous guide Kleene's theorem told you, as a fact, that the regular expressions and the finite automata describe exactly the same family of languages. A fact you cannot compute with is only half useful, so this guide turns the theorem into two concrete, crank-the-handle procedures. One direction takes a pattern and builds a machine that accepts precisely the strings the pattern denotes. The other takes a machine and squeezes out a pattern that describes precisely the strings it accepts.
Why bother with both? Because each direction is the workhorse of a different real task. Going from pattern to machine is what a search tool or a lexer does when you hand it a regex: it compiles the pattern into something it can run fast. Going from machine to pattern is how you prove things — once a language has any finite automaton, you have a guarantee that a regular expression for it exists, and the procedure even writes that expression for you. Together they are the engine room under the slogan 'regex equals automata'.
Pattern to machine: Thompson's construction
The trick to going from a pattern to a machine is to refuse to be clever. Recall from earlier in this rung that every regular expression is built from base cases (a single symbol, epsilon, or the empty language) glued together by exactly three operations — union, concatenation, and the Kleene star. So we build the machine the same way the pattern is built: one tiny gadget per piece, snapped together with the free moves you met last rung. The result is an epsilon-NFA, and the recipe is Thompson's construction.
Each gadget keeps one strict promise: exactly one start state and exactly one accept state, with no arrows leaving the accept state and none entering the start state from outside. That discipline is what lets the pieces snap together blindly, like LEGO bricks with studs in fixed places. A single symbol 'a' is two states with an a-arrow between them. Concatenation of A and B draws an epsilon-arrow from A's accept to B's start. Union of A and B adds a new start with epsilon-arrows into both, and a new accept that both old accepts reach by epsilon. The star wraps a machine in a new start/accept pair, with epsilon-arrows that let you skip it entirely or loop back to repeat it.
Thompson gadgets (S = start, A = accept):
symbol a : S --a--> A
epsilon : S --eps--> A
concat M.N : S_M ...(M)... A_M --eps--> S_N ...(N)... A_N
union M|N : eps eps
S ---------> S_M ...A_M ------\
| > A
\---------> S_N ...A_N --------/
eps eps
star M* : ___________eps__________
/ v
S --eps--> S_M ...(M)... A_M --eps--> A
^___________eps___/
(S --eps--> A also, to allow zero copies)Machine to pattern: state elimination
Going the other way feels harder — how do you read a tidy expression out of a tangle of states and arrows? The key idea is to let the arrows carry regular expressions instead of single symbols. A machine whose arrows are labelled by whole patterns is a generalized NFA (a GNFA). An ordinary automaton already is one: each arrow just happens to be labelled by a one-symbol pattern. Now we delete states one at a time, and every time a state leaves, we repair the arrows around it so that the language is preserved — the patterns on the surviving arrows grow to absorb the paths that used to pass through the deleted state.
- Tidy up first. Add a fresh start state with an epsilon-arrow into the old start, and a fresh single accept state with epsilon-arrows in from every old accept state. This guarantees one entry and one exit, with no arrows fighting them.
- Pick any state that is neither the new start nor the new accept, and prepare to rip it out.
- For that doomed state q, look at every pair of a state p coming in and a state r going out. The old route p -> q -> r reads: the label on p->q, then (q's self-loop label, starred, to allow looping any number of times), then the label on q->r.
- Add that combined pattern to the existing p->r arrow with a union (an OR). Concretely the new p->r label becomes (old p->r) | (p->q)(q->q)*(q->r). Then delete q and all its arrows.
- Repeat until only the start and accept states remain. The single arrow left between them is labelled by the regular expression for the whole machine's language.
The formula in step 4 is the whole secret, so read it slowly. To erase q you must account for every way of passing through it: enter on p->q, optionally loop on q's self-arrow as many times as you like (that is the star), then leave on q->r. Anything that already went straight from p to r still works, so you OR the two together. Because the order in which you delete states never changes the language — only the look of the final expression — you are free to delete in whatever order keeps the bookkeeping smallest.
The same idea as algebra: Arden's rule
There is a second, equivalent way to extract a pattern that feels like solving simultaneous equations, and it rests on one neat identity called Arden's rule. Write one equation per state, where the unknown is 'the set of strings that drive the machine from this state to acceptance' (or from the start to here — both versions exist). Each equation says: my language is the union of one symbol followed by the next state's language, over every arrow leaving me, plus epsilon if I am an accept state. Then you solve the system.
Arden's rule is the tool that breaks a self-reference. If a variable X satisfies X = A X | B — meaning 'X is some A's then more X, or else B' — then the unique smallest solution is X = A* B, provided A does not contain epsilon. Read it aloud: to reach a B, loop on A as many times as you like (that is the star), then finish with B. It is the algebraic twin of the star self-loop you used in state elimination; the two procedures are genuinely the same idea wearing different clothes, and they always agree on the answer (up to rewriting the expression with the algebraic identities from guide 2).
What the round trip actually proves
Put the two directions back to back and you have a real proof, not just a slogan. Thompson's construction shows every regular expression has a finite automaton; state elimination (or Arden's rule) shows every finite automaton has a regular expression. Neither direction loses or gains a single string. That two-way equivalence is exactly Kleene's theorem, now with the machinery to back it. And because we know all flavours of finite automaton — DFA, NFA, epsilon-NFA — accept the same class, you can start from whichever is most convenient and convert freely among all four representations.
Two honest reminders. First, all of this lives entirely inside the regular languages: converting back and forth never makes a language bigger, so a pattern like a* stays regular and stays infinite — remember, regular does not mean finite. Second, an automaton built by Thompson is an epsilon-NFA, so its conciseness is borrowed from nondeterminism, which is a design convenience and not free hardware; the subset construction that determinises it can in the worst case turn n states into 2^n. The conversions are always possible; they are not always small.
Finally, a bridge to the next guide. Real-world regex engines lean on exactly this pipeline — pattern, then NFA, then a deterministic simulation — which is why a well-written pattern searches text in time linear in the input. But engineering regex has bolted on features like backreferences and lookahead that no finite automaton can express, and those features can make matching blow up to exponential time. Guide 5 takes that warning seriously; what you have built here is the clean mathematical core that the engines start from before they wander off the map.