Finite Automaton Builder

Most people meet regular expressions as a search box trick. A cryptic line of punctuation finds every phone number in a file, and that is the end of the acquaintance. The idea underneath is older than the search box and a good deal stranger. A regular expression describes a machine that reads a string once, from left to right, and remembers nothing about it except which of a fixed handful of situations it is in.

That poverty is the point. A device with a fixed, finite set of states can be drawn on a page, checked by hand, compared with another, and shrunk to its smallest form by a procedure that always ends. Very few descriptions of computation allow all of that. The price is that some patterns people expect to write are simply out of reach.

Three descriptions of one thing

The word regular goes back to the logician Stephen Kleene. In a 1951 technical report, later published in 1956 under the title Representation of Events in Nerve Nets and Finite Automata, he described sets of strings he called regular events, and invited suggestions for a more descriptive term. The name stayed.

Kleene’s notation had three ways to build a set of strings from smaller ones. Put one after another. Offer a choice between two. Repeat something any number of times, including zero, which is the operation now called the Kleene star. Add the single symbols, the empty string and the empty set as raw material and the formal language of regular expressions is complete. Star binds tightest, then concatenation, then choice, so that ab*|c reads as a followed by any number of b, or else c.

The second description is a diagram. A finite state machine, in the wording of the NIST dictionary, is a model of computation made of a set of states, a start state, an input alphabet and a transition function that sends the current state and the next symbol to a next state. In the deterministic kind there is at most one move for each state and symbol, and many treatments require exactly one. The machine reads the string, follows the arrows, and accepts if it stops in a marked state.

The third description loosens the second. A nondeterministic machine may have several moves for the same symbol, or none, and may also change state without reading anything at all. It accepts when at least one of its possible paths ends in an accepting state. Michael Rabin and Dana Scott introduced these machines in 1959 and showed in the same paper that they recognise nothing a deterministic machine cannot.

The equivalence of regular expressions and finite automata is known as Kleene’s theorem. It says the written notation and the diagrams are two views of one family of languages: every expression has a machine, and every machine has an expression. The rest of the subject is a set of procedures for travelling between the views, and each procedure can be carried out with a pencil.

From expression to machine

The first journey was mapped by Ken Thompson in a 1968 paper in Communications of the ACM, and he built Kleene’s notation into the text editor QED. His construction works on the structure of the expression. Each symbol becomes two states joined by one labelled arrow. Each operator glues smaller machines together with arrows that consume no input, the empty moves.

The pieces are small enough to memorise. A choice gets a new start state with an empty move into each alternative and a new final state that both alternatives fall into. A star gets a new start and a new end, a way in, a way around for zero repetitions, a way back for more, and a way out. Concatenation costs nothing: the end of the first machine simply becomes the start of the second.

The result is orderly. No state has more than two arrows leaving it, and the number of states grows in step with the expression. Counting s for the operators and symbols other than brackets and c for the concatenations, the machine has 2s minus c states. Take (a|b)*abb, the strings over a and b that end in abb. It has seven such signs and three concatenations, so the machine has 11 states, and that is the count a careful construction produces.

A machine full of empty moves is awkward to run by hand, because it can be in many states at once. The honest way to simulate it is to keep the whole set of states it might be in, and after each symbol to replace that set with everything reachable from it. Thompson’s paper introduced that multiple state simulation.

The cost of certainty

Rabin and Scott’s argument turns that bookkeeping into a machine of its own. Let every set of nondeterministic states be one state of a new, deterministic machine. Its start state is everything reachable from the old start by empty moves alone. Its move on a symbol goes to the set of everything reachable from the current set by that symbol and then by empty moves. A set is accepting when it contains an accepting state.

This is the subset construction, or powerset construction, and its name is a warning. A machine with n states has 2 to the power n subsets. In practice only the subsets that can actually be reached from the start are ever built, and usually there are few. For (a|b)*abb the 11 nondeterministic states give just five reachable sets, so the deterministic machine has five states.

Sometimes the explosion is real. Consider the strings over two symbols in which the n-th symbol from the end is a particular one. A nondeterministic machine can guess the right moment and then count n steps, so it needs about n states. A deterministic machine cannot guess. It must remember the last n symbols it read, and there are 2 to the power n possibilities, each demanding its own state. With n equal to 10, the smallest deterministic machine has 1,024 states.

The two outcomes are worth holding side by side. Nondeterminism is not more powerful, since both kinds of machine recognise exactly the regular languages. It can be exponentially more concise. Which case a given pattern falls into depends on how much of the past the language forces a reader to keep.

The smallest machine is unique

The subset construction rarely gives the smallest deterministic machine. Two of its states may behave identically: whatever string comes next, both lead to acceptance or both to rejection. Such states can be merged without changing the language. States that can never lead to acceptance at all collapse into a single dead state, and states no input can reach are simply removed.

Edward Moore’s 1956 method finds the mergers by refinement. Begin with two groups, accepting and not. Then split any group whose members disagree about which group some symbol sends them to, and repeat until a pass changes nothing. John Hopcroft’s 1971 algorithm reaches the same partition faster, in time proportional to the number of states times the alphabet size times a logarithm. For (a|b)*abb the five states become four, so the whole journey reads 11, 5, 4.

What makes the exercise more than tidying is a theorem named for John Myhill and Anil Nerode, proved at the University of Chicago in 1957. A language is regular exactly when its strings fall into finitely many classes of interchangeable prefixes. The number of classes is the number of states in the minimal deterministic machine, and that machine is unique apart from the names of its states.

Uniqueness gives a decision procedure. To ask whether two expressions mean the same thing, minimise both and compare. If the machines match state for state, the languages are equal. If they do not, walking the two machines together finds the shortest string that one accepts and the other rejects. The expressions (a|b)*abb and (a*b)*abb look interchangeable, yet the second cannot begin with two a in a row before the ending. The shortest string that separates them is aabb.

Where the search box parts company

Everything above holds for the formal notation only. The patterns in programming languages share its punctuation and go further. The best known extension is the backreference, which matches again whatever an earlier bracketed group matched. The pattern (.+)\1 matches any string that is some text written twice.

That language is not regular, and it is not even context-free. A finite machine would have to remember an arbitrarily long first half to check the second, and it has nothing to remember it with. Matching with backreferences is NP-complete, in Russ Cox’s summary, which is why engines that offer them fall back on trying alternatives one at a time and can take exponential time on unlucky input.

Other everyday features sit outside the model for milder reasons. Anchors and lookahead are assertions about position, not symbols. Lazy quantifiers choose which of several matches to report, a question that does not arise for a machine that only answers yes or no. The interoperable format published as RFC 9485 in 2023 is a deliberate return to the core: it leaves out capture groups, lookahead and backreferences and offers only a true or false match.

So the builder beside this essay refuses those constructs and says why. It also has practical ceilings: an expression of 200 characters, an alphabet of 26 symbols, and a deterministic machine of 5,000 states, beyond which it stops and reports. It cannot read a programming language’s pattern syntax, and a picture is drawn only for machines small enough to read.

What remains inside those limits is a rare thing in computing, a notation whose every question has an answer. Does this string match? Run the machine. Is there a smaller machine? Minimise it and know that the result cannot be beaten. Do two patterns agree? Compare, and receive either a proof or a counterexample of the shortest possible length.