Two states per operator

This collection has one automaton in it and it reads a text to produce a parse. The parse in one pass of the text is that machine, and its states are positions in a suffix structure.

A regular-expression machine reads a text to answer a question, and the question is handed in at run time. That is the difference that makes the machine’s size a measurement: a pattern-matching automaton is built from a fixed pattern and a regular-expression machine is built from a small program somebody supplies.

The three kinds of state #

There are exactly three and the whole construction follows from having no others.

A test state carries a character predicate — a literal, a class, a wildcard — and has one successor. Reading a matching character moves to the successor; reading anything else kills that thread.

A split state carries two successors and no predicate. It is followed for free, without reading anything.

The accepting state has no successor. Reaching it means the expression matched.

That is the whole machine. On the twelve-operator expression drawn above: fourteen test states, nine splits, one accepting.

The rules #

Each construct compiles to a fragment — a start state and a set of dangling outputs to be patched later — and the rules add a bounded number of states each.

A character, a class or a wildcard is one test state with one dangling output.

A concatenation builds both halves and patches the first’s outputs to the second’s start. No new state.

An alternation builds both halves and adds one split pointing at the two starts. Its outputs are the union of the two halves’. One new state.

An optional adds one split: one branch into the sub-machine, one bypassing it. One state.

A closure adds one split whose first branch enters the sub-machine and whose second bypasses; the sub-machine’s outputs are patched back to the split. One state.

A plus is the same split with the entry point moved to the sub-machine. One state.

So each operator adds zero or one state, each atom adds one, and no rule duplicates an existing fragment. The machine’s size is the number of atoms plus the number of operators plus one, which is linear in the expression’s length.

The construction is also incremental, which is worth noting because it is what makes the linear time as well as the linear size. Each rule builds its fragment from its children’s fragments without inspecting them: a concatenation patches one set of dangling outputs to a start state, which is one pass over that set.

So the total work is the number of patches, and each output is patched exactly once — a fragment’s outputs are consumed by the rule above it. That gives O(m) time with no traversal of the machine at any point.

A construction that had to examine a sub-machine — to check whether it accepts the empty string, say — would still be linear in size and would not obviously be linear in time. Thompson’s does not, and the check that it does not is that the recursion never reads a fragment’s states, only its start and its outputs.

Why “no rule copies” is the whole of it #

The linearity is not a happy consequence of a well-chosen construction; it is the property that distinguishes this construction from the obvious alternative.

An expression like (a|b){3} — three copies of an alternation — is written out as three copies, so its machine is three times one alternation’s. That is the expression being longer, not the construction duplicating.

What a construction could do is expand a closure by unrolling it, or expand an alternation by distributing it over a concatenation. Both produce equivalent machines and both multiply. The rules above do neither: they add a split and let the non-determinism carry what a distribution would have written out.

That is what the split state is for. It is the mechanism by which a machine represents a choice without enumerating its consequences, and enumerating the consequences is exactly the subset construction — which is where the exponential lives. The exponential is in the expression is where that is measured.

There is a second construction worth naming because it is the one a bit-parallel matcher uses and it has a different linearity.

Glushkov’s construction produces a machine with exactly one state per character position of the expression, plus a start — so it is smaller than Thompson’s by a constant, and it has no epsilon transitions at all. Every transition consumes a character.

That absence is what makes it bit-parallel: with no free edges the state set advances by a masked shift, and one character is a handful of word operations rather than a fixed-point iteration.

The cost is that its transitions are dense: a state can go to many others, so the transition relation is a set of masks rather than a successor per state, and building it is quadratic in the expression rather than linear.

So the two constructions trade construction time against step simplicity, and this collection builds Thompson’s — which means its bit-parallel simulation is a constant-factor improvement rather than the technique the literature means.

What a step costs #

A machine with split states is non-deterministic: reading a character can leave it in several states at once, so a simulation carries a set.

One step is: for each state in the set, test the character and follow the successor if it matches; then close the resulting set under the split edges, which is a reachability walk over free transitions.

So a character costs the set’s size, plus the closure. That is the machine being linear in the expression paid back at run time — a machine with m states can be in up to m of them, so a step is O(m) and a text of length n costs O(nm).

That product is the whole of the trade this strand is about. The alternative is to precompute which sets are reachable, so a step is one lookup and the sets have to be enumerated, which is where the table starts paying.

The closure, and why it is not a shift #

The epsilon closure is the part that stops this being an instruction rather than a loop, and it is worth being precise because a reader who knows bit-parallel string matching will expect otherwise.

In a Shift-Or matcher the state set is a bit mask and one step is a shift and an or, because the machine’s transitions are local: state i goes to state i + 1.

Thompson’s splits are not local. A split at state 20 can point at states 3 and 45, so following the free edges is not a shift — it is a reachability computation over an arbitrary graph, iterated to a fixed point.

That is why the bit-parallel simulation in this strand is a constant-factor improvement rather than a change of class. What a character costs on four machines measures it: 45.1 word operations a character against the state-set simulation’s 52.6, on a machine with one word.

A construction whose transitions are local exists — Glushkov’s — and it is what a genuinely bit-parallel regular-expression matcher uses. This collection builds Thompson’s, and the honest consequence is that its bit-parallel machine is not the one the literature means.

What the picture shows #

The plate lays the states out in rows and draws an edge for every transition. Two things are visible in it.

The splits are the pale edges and there are as many pale edges as split states times two. They are followed for free, so a character crosses only the dark ones — and the dark edges are the test states’ successors, one each.

The machine is a chain with detours. The expression’s concatenation is a spine and each alternation or closure is a place where the spine forks and rejoins. That shape is what makes a Thompson machine easy to read and hard to make bit-parallel: the forks are where the locality goes.

What a set-carrying step actually does #

The simulation is short enough to describe completely, and describing it makes the two costs visible.

Start with the closure of the start state — every state reachable from it by free edges.

For each character: walk the current set, testing each state’s predicate; collect the successors of the ones that match; close that collection under free edges; and that is the new set.

Two loops. The first is over the current set and is the state visits; the second is the closure and is the transitions. Both are charged separately, because they are different things — a visit is a predicate test and a transition is a pointer followed — and a single “operations” number would make them interchangeable.

Measured on a 24-state machine over four thousand characters: 119,266 state visits and 59,636 transitions, so 43.7 operations a character. That the transitions are exactly half the visits is not a coincidence: every split state visited during a closure pushes two successors, and the closure visits each state once.

The closure is a stack-based reachability walk with a visited set, and it is where a naive implementation goes quadratic — a closure that re-enters an already-closed state loops on a machine with a cycle, which every closure operator produces.

What is checked #

Four machines are built here from one expression and the primary check is that they agree.

Five expressions, sixteen texts each, four machines plus a backtracking matcher: eighty comparisons, and all five agree on every one.

That is a stronger check than it looks, because the five are genuinely different objects. The non-deterministic simulation carries a set; the deterministic one carries an integer; the lazy one carries an integer and builds states as it goes; the bit-parallel one carries a word; and the backtracking matcher carries a call stack.

An expression they disagreed about would be an expression one of them compiles wrongly, and the construction is where that would happen: a patch applied to the wrong output set, a closure whose back-edge points at the wrong split.

The construction also asserts its own shape: every state is a test, a split or the accepting one, and the counts sum to the machine’s size. That is a weak check and it catches the class of bug where a rule forgets to register a state, which is the one that would make the size measurement wrong while leaving the machine correct.

What is not in this language #

The parser here handles concatenation, alternation, three closures, a wildcard, a bracketed class and parentheses. Deliberately small, and one omission is the reason the whole strand is possible.

No backreferences. A pattern like (a*)b\1 requires the matcher to remember what the first group captured and compare against it later, and that is not a regular language — it cannot be recognised by any finite automaton, and the machines here would not be able to express it.

Every production engine that supports backreferences is therefore unable to use these machines for such patterns, and most use a backtracking matcher for all patterns as a result. That decision is what the folklore is about a matcher is about, and it is the reason a language feature nobody uses much determines the performance of the ones everybody does.

No anchors, no lookahead, no lazy quantifiers. Anchors are easy to add and the rest are not regular either.

So the language here is the regular one, and its machines have the properties this strand measures. An engine supporting more is measuring something else.

Where this sits in the automaton strand #

This collection’s automaton field has two essays before this one and they are about a different kind of machine, which is worth marking because the word covers both.

Every substring in fewer states is about a machine built from a text, recognising its substrings — a suffix automaton, whose states are equivalence classes of positions and whose size is linear in the text.

One pass for every pattern at once is about a machine built from a set of patterns — an Aho–Corasick automaton, whose states are the patterns’ prefixes and whose failure links are what make one pass suffice.

Both are deterministic by construction and both have sizes that are linear in their input.

This machine is built from an expression, is non-deterministic, and has a deterministic form whose size is not linear in anything. That is the new thing the strand adds, and it is the reason the field’s third machine needs four essays rather than one: the others have one representation and this has several with different costs.

The construction as a measurement #

The machine’s size is a measurement in this collection rather than a constant, and it is worth saying why that is unusual enough to matter.

Every other structure here is built from data: a suffix array from a text, a wavelet tree from a sequence, a parse from a corpus. Their sizes are functions of the data and the data is fixed for a measurement.

A regular-expression machine is built from a program, supplied at run time by whoever is querying. So its size is a function of an input the system does not control, and a structure whose size is a function of user input has a failure mode nothing else here has: a user can ask for a machine too large to build.

For the non-deterministic machine that is bounded — linear in the expression, so an expression of a thousand characters gives a machine of about two thousand states. For the deterministic one it is not, and the exponential is in the expression measures it at 2^(k+1) on a family with a twenty-character expression reaching five hundred and twelve states.

That is the practical reason a production engine’s deterministic construction is lazy and capped: not because the exponential is theoretical but because the input is untrusted.

Linear in the expression, linear in the text #

The two linearities are separate claims and both are worth stating because the folklore confuses them.

Linear in the expression: the machine has O(m) states and is built in O(m) time. That is the construction, and it is what this essay is about.

Linear in the text: a simulation advances a state set once per character, so a text of length n takes O(n) steps whatever the expression is. Each step costs O(m), so the total is O(nm) — linear in n with a constant that is the machine’s size.

A backtracking matcher has neither. It can take exponential time in the text on a fixed expression, which the folklore is about a matcher measures at a factor of twelve thousand on a twenty-character input.

The distinction matters because “regular expressions are slow” is a claim about the second linearity failing, and no machine in this strand fails it.

What does fail in this strand is a different thing entirely: the deterministic machine’s size, which is exponential in the expression. That is a real cost, it is measured, and it is in the expression rather than in the text — so a system meeting it pays once at construction rather than repeatedly at run time.

Three quantities, then, and keeping them apart is most of what this strand is for. The machine’s size in the expression: linear for the non-deterministic form, exponential for the deterministic one. The run time in the text: linear for every machine here. And the run time in the expression: linear per character for the non-deterministic form, constant for the deterministic one.

A sentence about regular expressions being slow or fast has to say which of the three it is about, and almost none does.

That is the whole of what this essay is for. The construction is standard, the machine is fifty years old, and nothing about either is a finding. What the strand needs it for is a shared object: four machines measured against each other need to be four representations of one language, built from one expression, and Thompson’s construction is where they all start.