Regular expressions to automata, from Thompson to minimal DFAs

Three descriptions of the same languages

A regular expression describes a set of strings with three operations: union $R \mid S$, concatenation $RS$ and the Kleene star $R^*$, starting from single symbols, ε and $\varnothing$. A DFA recognises a set of strings by reading them one symbol at a time with a fixed amount of memory. An NFA is like a DFA that may have several moves (or none) for a symbol, and ε-moves that read nothing; it accepts if some sequence of choices ends in an accepting state.

The theorem is proved by constructions that convert one notation into another, and those constructions are exactly what lexer generators and regular-expression engines run:

The opposite direction, from an automaton back to an expression, uses state elimination: remove states one at a time, labelling the edges that bypass them with regular expressions, until only a start and an accepting state remain.

Step 1: regular expression to NFA

Thompson’s construction builds an NFA for each sub-expression and glues them together. A symbol becomes two states joined by that symbol. Concatenation links one fragment’s end to the next one’s start with an ε-move. Union adds a new start state that branches by ε into both alternatives, and a new end state they both lead to. Star adds a back edge for repetition and a skip edge for zero repetitions.

For (a|b)*abb the result has 14 states and 16 transitions, 11 of them ε-moves. States 0–3 are the fragments for a and b, 4 and 5 are the union, 6 and 7 the star, and the three symbols a, b, b follow. The start state is 6 and the only accepting state is 13. The regex to NFA converter builds it one fragment at a time.

The construction is linear: each symbol or operator adds at most two states, so an expression of length $m$ gives at most $2m$ states. Every state has at most two outgoing transitions, and the single accepting state has none.

Step 2: ε-closures

Before reading any input, the NFA can already drift along ε-moves. The ε-closure of a set of states is everything reachable from it by ε-moves alone. From the start state 6:

Reading a from any of those states is possible only from the states with an a-transition, which gives $\text{move}(\cdot, a) = \{1, 9\}$; then the closure is taken again. Simulating an NFA is just this, repeated: keep the set of live states, and after each symbol replace it with the ε-closure of its moves.

Step 3: the subset construction

A DFA cannot be in several states at once, but it can have one state for each set of NFA states. The subset construction names each reachable set, starting from the closure of the start state, and fills in a table of moves until no new sets appear. For our example it finds 5 sets:

Only E contains the NFA’s accepting state 13, so it is the only accepting DFA state. In the worst case the construction can produce $2^n$ states from an $n$-state NFA, but here, as usual, only a handful of the $2^{14}$ possible subsets are reachable.

Step 4: minimisation

Two DFA states are equivalent when every string leads both to acceptance or both to rejection. Merging equivalent states never changes the language. Moore’s algorithm finds them by refining a partition:

1. accepting vs not: {A, B, C, D} {E}
2. round 1: {A, B, C} {D} {E}
3. round 2: {A, C} {B} {D} {E}

Each round splits a group whenever two of its states move into different groups on the same symbol. When no group splits, each group is one state of the minimal DFA. Here states A and C are merged, leaving 4 states: one for each of “no progress”, “just read a”, “just read ab” and “just read abb”. That is the DFA you would design by hand for “ends in abb”.

The minimal DFA is unique up to the names of its states (the Myhill–Nerode theorem). So to test whether two regular expressions mean the same thing, minimise both DFAs and compare: an algorithm that decides regex equivalence.

Where this pipeline runs

• Lexer generators such as lex and its descendants take a list of token patterns, build one NFA for all of them, determinise and minimise it, and emit a table-driven scanner that reads each character once.
• Regular-expression engines choose different points on the pipeline. Some simulate the NFA directly (Thompson’s original approach, linear time in the input). Others build DFA states lazily as the input demands them, to avoid the exponential worst case. Backtracking engines, used where back-references are needed, can take exponential time on patterns such as (a|a)*b.
• Verification and network filtering use the closure properties: intersect, complement and test for emptiness, all on DFAs.

Try it

• Regex to NFA converter: step through Thompson’s construction and test strings on the NFA.
• NFA to DFA converter: the subset construction and minimisation, from a regex or your own NFA.
• DFA simulator: edit the resulting DFA and test it.

References

1. S. C. Kleene, “Representation of events in nerve nets and finite automata”, in Automata Studies, Princeton University Press, 1956.
2. K. Thompson, “Programming techniques: Regular expression search algorithm”, Communications of the ACM 11(6), 1968. doi:10.1145/363347.363387
3. M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM Journal of Research and Development 3(2), 1959. doi:10.1147/rd.32.0114
4. A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Pearson, 2006. Chapter 3.