Kleene's theorem — regex ⟺ finite automaton

Parent: regular-equivalences

Kleene (1951)

A language is denoted by a regular expression iff it is recognized by a finite automaton.

Both directions are constructive:

regex → automaton: Thompson's construction

Build a small ε-NFA per operator, inductively:

• symbol a: two states, one a-edge;
• union R|S: a new start with ε-edges into the sub-automata for R and S;
• concatenation RS: ε-edge from R's accept to S's start;
• star R*: ε-edges to loop back and to skip. Linear in the size of the regex.

automaton → automaton: subset construction

An NFA → an equivalent DFA whose states are sets of NFA states (up to 2ⁿ). This makes "finite automaton" unambiguous — determinism costs only size.

automaton → regex: state elimination (Arden's rule)

Rip states out one by one, relabelling each remaining edge with a regex; a self-loop X = A X | B is solved by Arden's rule X = A*B. That solution is a least fixed point — the Kleene star is the fixed-point operator, so Kleene's theorem quietly uses Kleene's fixed point.

and grammars

A → aB = a transition A --a--> B, terminal-only rules = acceptance (regular-grammar) — the third formalism folds in for free.