KLEENE’S THEOREM regex, NFA, DFA: three faces of one class
A regular expression, a finite automaton, and the class of regular languages are the same thing said three ways: every regex has an equivalent automaton, every automaton an equivalent regex, and both define exactly the regular languages. Kleene proved the equivalence in 1951 — the theorem that makes “regular” a robust idea rather than an accident of notation, and gives the star its name.
THE TECHNIQUE one language, three descriptions, all agree
Take the language a*b. Its regex, its NFA/DFA (a transition table), and a direct membership test must all agree on every string. Feed several strings through all three and watch them return the same verdict — the equivalence made concrete: live demo
HISTORY & CREDIT Stephen Kleene, RAND 1951
“Kleene invented regular expressions for text search.” — no. He introduced them to describe the behaviour of McCulloch-Pitts neural nets (1943), as “regular events”; text-search regex (Thompson’s grep) came two decades later. The Kleene star is his; the notation’s fame is Thompson’s. cited
1943 · McCulloch & Pitts — a formal model of neural nets, the “events” Kleene set out to characterise. 1951 / 1956 · Stephen Kleene — “Representation of Events in Nerve Nets and Finite Automata” (RAND memo 1951, published 1956): regular events = finite-automaton behaviour, the star, and the theorem. 1968 · Ken Thompson — compiles regexes to code for text search (grep’s ancestor), making the notation famous.
The theorem is a closure statement: because the three descriptions coincide, regular languages are closed under union, concatenation, star, intersection and complement — every operation you can express one way survives translation to the others. Kleene 1951
RECOMMEND FOR I-13 three descriptions agree, computed
The DFA side of the equivalence for a*b runs on the canonical compiler; regex and automaton return the same verdict on every string:
$ i13 run dfa.i13 # a*b as a transition table; matches the regex on every input
aab -> state 1 (accept) -- regex a*b: matches (a a then b)
aa -> state 0 (reject) -- regex a*b: no trailing b -> no match
Recommend: Kleene’s theorem is LIT in its consequence for I-13 — verified that the automaton for a*b (a transition table run natively) agrees with the regular expression on every test string (aab accept, aa reject). It is the license for the whole batch: because regex, NFA (Glushkov 176), derivative-DFA (Brzozowski 177) and minimal DFA (Hopcroft 178) all denote the same class, an I-13 regex engine may pick whichever representation is cheapest for each operation and know the answer is the same. The star it names is the one unbounded operator in an otherwise finite world — the honest edge of what a finite machine can describe.