In everyday practice, regular expressions are a tool for searching text. In the theory of computation they play a more precise role: they are a formal language for describing languages, with minimal syntax and rigorous semantics. Kleene's theorem states that regular expressions describe exactly the languages recognized by finite automata. Two formalisms born with different aims, one declarative and one operational, coincide.
Regular expressions in the theoretical sense
Over an alphabet Σ, regular expressions are defined inductively:
- ∅ is a regular expression and denotes the empty language;
- ε denotes the language containing only the empty string;
- every symbol a ∈ Σ denotes the language {a};
- if R and S are regular expressions, so are R | S (union), RS (concatenation) and R* (Kleene star, that is zero or more repetitions).
Everything else is shorthand. R+ is RR*, R? is R | ε. Many constructs in modern text-search engines, such as backreferences, step outside this framework and can describe non-regular languages: worth remembering when comparing theory and tools.
The statement
Kleene's theorem has two directions:
- For every regular expression R there is a finite automaton recognizing L(R).
- For every finite automaton M there is a regular expression denoting L(M).
Since we already know NFAs and DFAs are equivalent, we can work with whichever automaton is more convenient in each direction.
From expression to automaton: Thompson's construction
The first direction is proved by induction on the structure of the expression, building an NFA with ε-transitions. Every automaton built has a single start state and a single final state, which makes the pieces easy to glue together.
- Symbol a: two states joined by a transition labelled a.
- ε: two states joined by an ε-transition.
- ∅: two states with no transition at all.
- Union R | S: a new start state with ε-transitions to the start states of R and S, and ε-transitions from their final states to a new final state.
- Concatenation RS: an ε-transition from the final state of R to the start state of S.
- Star R*: a new start and a new final state; ε from start to final (zero repetitions), ε from the new start to R's start, ε from R's final back to R's start (repeat) and to the new final (exit).
The number of states grows linearly with the length of the expression: each operator adds at most two states. From here one can move to a DFA with the subset construction if needed.
From automaton to expression: state elimination
The second direction is less intuitive. The most readable method is state elimination on a generalized automaton, whose transitions are labelled with regular expressions rather than single symbols.
- Add a new start state and a new single final state, joined to the original automaton by ε.
- Pick an internal state q to eliminate.
- For every pair of states p and r with an edge p → q labelled A, a possible self-loop on q labelled B and an edge q → r labelled C, add (or join with |) an edge p → r labelled A B* C.
- Remove q and repeat until only the start and final states remain.
The label of the single remaining edge is the expression we want.
An example
Take the DFA over {0, 1} with two states, A (start) and B (accepting): from A on 0 stay in A, from A on 1 go to B, from B on 1 stay in B, from B on 0 go back to A. It recognizes strings ending in 1.
Add S → A with ε and B → F with ε. Eliminate A: edge S → A is ε, the loop on A is 0, edge A → B is 1, so S → B becomes 0*1. There is also the path B → A → B: edge B → A on 0, loop 0, edge A → B on 1, which joins the existing loop on B: the loop becomes 1 | 00*1.
Eliminate B: S → F becomes 0*1 (1 | 00*1)*. It is a correct expression for "strings ending in 1", though not the most compact: (0 | 1)*1 describes the same language. State elimination guarantees correctness, not elegance, and the elimination order strongly affects the length of the result.
Why it matters
Kleene's theorem has concrete consequences:
- Closure: regular languages are closed under union, concatenation and star, as is obvious from expressions, and under complement and intersection, as is obvious from DFAs. Combining the two views yields closure under all these operations.
- Tools: lexical analyzer generators start from regular expressions and produce automata; that is exactly the first direction of the theorem.
- Comparison: to decide whether two regular expressions are equivalent, convert both to minimal DFAs and compare them. The problem is decidable, although in the worst case the cost grows quickly.
In short
- Theoretical regular expressions use only ∅, ε, symbols, union, concatenation and star.
- Kleene's theorem says they describe exactly the languages recognized by finite automata.
- Thompson's construction turns an expression into an NFA with a linear number of states.
- State elimination turns an automaton into an expression, correct but not always compact.
- Combining the two perspectives makes the closure properties of regular languages easy to prove.
