Kleene's theorem

Throughout this domain you meet several different-looking ways to describe languages: deterministic machines (DFAs), nondeterministic machines (NFAs), and now algebraic formulas (regular expressions). It would be remarkable if they all captured exactly the same set of languages, no more, no less. Kleene's theorem says precisely that: regular expressions and finite automata are equally powerful.

Stated carefully, a language is denoted by some regular expression if and only if it is recognized by some finite automaton. The 'if and only if' has two directions, each proved by an explicit construction. Forward: from any regular expression you can build an equivalent epsilon-NFA, gluing together small machines for each operator (the Thompson construction). Backward: from any finite automaton you can extract an equivalent regular expression, by repeatedly removing states from a generalized NFA (state elimination) or by solving language equations with Arden's rule. Because both constructions are algorithms, the equivalence is not just abstract; you can mechanically convert one representation into the other.

This is the third equivalent face of regularity, alongside the DFA-equals-NFA result. It is why 'regular language' has a single, robust meaning regardless of which formalism you choose, and it is the theoretical foundation for tools like lexer generators, which let you write token patterns as regular expressions and compile them into fast automata. Named after Stephen Kleene, who proved it in 1951; the same Kleene whose name the star carries.