The exponential is in the expression

A non-deterministic machine can be in several states at once. A deterministic one has a state per set of them, so its size is bounded by two to the power of the non-deterministic machine’s.

That bound is usually described as pathological. It is met, exactly, by a family short enough to type.

The family #

(a|b)*a(a|b)^k — anything, then an a, then exactly k more characters.

Its non-deterministic machine has 2k + 14 states: twelve for the prefix and two per (a|b).

Its deterministic machine has 2^(k+1) states. At k = 8 that is 512, and the measurement is 512 — not approximately, not asymptotically, but the bound met.

Why it is met #

A deterministic machine reading this expression must, at every position, know whether the character k back was an a. It must also know whether the character k − 1 back was, and k − 2, and so on down to the current one — because any of them could turn out to be the a that starts the tail.

So the machine has to remember the last k + 1 characters’ worth of “was it an a”. That is a bit each, so 2^(k+1) distinct things to remember, and a machine with fewer states could not distinguish two histories that differ.

That is not an artefact of the subset construction. It is a lower bound on any deterministic machine for this language, by the standard argument: two inputs leading to the same state must have the same future acceptance behaviour, and these 2^(k+1) histories do not.

So the exponential is a property of the language rather than of the construction, and no cleverer determinisation avoids it.

The argument is worth doing concretely at k = 2, where the whole machine fits in a sentence. The expression is (a|b)*a(a|b)(a|b) — anything, an a, two more characters.

Reading a text, the machine must know whether the character two back was an a and whether the character one back was, because either could be the one the pattern needs. It must also know about the current character for the next step.

Three bits, eight states, and the measured deterministic machine has eight. At k = 3 it has sixteen; at k = 4, thirty-two.

That the count doubles per operator rather than growing by a constant is the whole distinction between this and every other structure in this collection, whose sizes are linear or logarithmic in something.

The other family #

A literal of the same length — a fixed string of k + 2 characters — has a deterministic machine of k + 3 states.

At k = 8 that is eleven. Against the blowup family’s five hundred and twelve.

Both are “a regular expression of length m”. Their non-deterministic machines are 30 and 11 states — within a factor of three. Their deterministic machines differ by a factor of 46.5.

The literal’s eleven states are worth a sentence because they are the case everybody’s intuition is built on.

A deterministic machine for a fixed string of m characters has m + 1 states: one per prefix matched. That is the Knuth–Morris–Pratt automaton, and its transitions on a mismatch go to the longest prefix that is also a suffix of what has been read.

So for a literal, “determinise” costs nothing at all — the machine was already deterministic in shape and the subset construction produces one state per set that happens to be a singleton.

That is why string matching feels like a solved problem and regular-expression matching does not. The same construction on the two inputs produces a machine of m + 1 states and one of 2^(k+1), and the difference is whether the pattern contains an unbounded choice.

What a state count without a family says #

Nothing usable, which is the point of drawing two lines.

A measurement of one family reports either that the subset construction is fine — the literal — or that it explodes — the blowup family. Both are true of what they measured and neither transfers.

That is the same shape as several results in this collection: a saving quoted without its collection is a compression figure that depends on the corpus, and two at binary, five at twenty-six is a factor that depends on the alphabet.

Here the dependence is on the expression, which is user input, and that makes it worse: a system cannot choose its expressions the way it can choose its corpus.

The bound as a lower bound #

The argument above is worth restating as the lower-bound proof it is, because this collection has a habit about such things and it applies.

Take the 2^(k+1) histories — every combination of “was the character i back an a” for i from 0 to k. Two different histories can be distinguished by a suffix: if they differ at position i, then feeding i more characters makes one of them accept and the other not.

So no two histories can lead to the same state of any correct deterministic machine, and the machine has at least 2^(k+1) states.

That is a Myhill–Nerode argument, and its shape is the one this collection uses for every floor it establishes: exhibit a set of inputs that must be distinguished, and the machine needs at least that many states.

The floor under every comparison sort is the same shape on a different object — count the leaves a decision tree must have — and a floor one pass cannot get under is the streaming version.

The habit in all three: a floor is established by counting what must be distinguished, and it applies to every algorithm rather than to the one in hand.

The rejection test #

The check requires the two families to differ by a wide margin in the deterministic size and to be close in the non-deterministic size.

Both halves are needed. Without the second, a family whose non-deterministic machine were also enormous would pass — and the claim is about the subset construction specifically rather than about one family being complicated.

Measured at k = 8: deterministic 512 against 11, a factor of 46.5; non-deterministic 30 against 11, a factor of 2.7.

So the two families are comparable as expressions and incomparable as deterministic machines, which is exactly the claim.

What the measurement adds to the proof #

The lower bound is a proof and the measurement is a measurement, and it is worth being clear about what the second adds to the first.

The proof says a correct deterministic machine needs at least 2^(k+1) states. It does not say the subset construction produces that many — a construction could produce more, by generating unreachable or duplicate states, and a naive one does.

The measurement says the construction produces exactly 2^(k+1), which means it produces no unreachable states and no duplicates. That is a statement about the implementation: subsets are interned by their sorted membership, so two ways of reaching one set give one state.

So the proof bounds the language and the measurement checks the code, and the check is an equality: the state count must equal the predicted 2^(k+1) at every k, exactly.

A construction producing 2^(k+1) + 3 states would be correct and would be generating something it should not, and only an exact check finds it.

That division — a bound for the problem and an equality for the implementation — is the habit this collection settles on wherever a closed form is available. Most of the time none is, and the check is a comparison against a reference implementation instead.

What “exactly 2^(k+1)” is evidence of #

A measured size matching a bound to the state is worth more than a size close to it, and it is worth saying why.

The subset construction reaches every subset that is reachable, and most bounds of this kind are loose because most subsets are not. A family reaching all of them has the property that its non-determinism is independent across positions: the answer to “was character i back an a” is unconstrained by the answers for other i.

(a|b)*a(a|b)^k has that by construction — the (a|b) allows either character freely — so every combination of the k + 1 bits occurs and every subset is reachable.

Changing one thing breaks it. (a|b)*a(ab)^k constrains the tail, so most combinations do not occur and the deterministic machine is far smaller than 2^(k+1).

So the family is not merely bad; it is maximally bad, and it is a witness rather than a typical case. What a typical expression’s deterministic machine costs is a different question that this strand does not answer.

The table’s size in bits is worth putting beside its state count, because a state is not a unit anybody pays in.

A deterministic machine’s table is one state identifier per alphabet symbol per state, plus an accepting bit. At 512 states over two symbols that is 512 × 2 × 10 + 512 = 10,752 bits — about a kilobyte and a third.

At k = 16 it would be 65,536 states and about two megabits. At k = 24, sixteen million states and half a gigabit.

So the expression (a|b)*a(a|b)^24 is fifty-one characters long and its deterministic machine does not fit in memory. That is the practical form of the bound, and it is why a cap is necessary rather than prudent.

On a byte alphabet the table is 128 times wider, so the same expression at k = 16 would be a quarter of a gigabit. Real engines are on byte alphabets.

What the lazy construction does #

A production engine does not build the whole table. It builds a subset state the first time a character asks for it and keeps a bounded cache.

That is usually described as making the exponential go away. It does not: a cache below the reachable set measures how much of the lattice a random text reaches, and on this family at k = 8 the answer is all 512 states, by sixteen thousand characters.

So the lazy construction decides when the exponential is paid rather than whether. On a short text it is never reached; on a long one it is reached in full; and the cache’s size decides what happens in between.

That is a more useful statement than “it goes away” and it is what the strand’s two later essays are about.

Where the bound comes from #

The subset construction’s bound is 2^m for a non-deterministic machine of m states, and this family’s deterministic machine is 2^(k+1) against a non-deterministic machine of 2k + 14.

So the measured size is 2^(k+1) and the bound is 2^(2k+14) — the family reaches the language’s lower bound rather than the construction’s upper one, and those differ by a huge factor.

That distinction is worth keeping straight because both are called “the exponential blowup”. The construction’s bound is 2^m and is essentially never approached; the language’s requirement here is 2^(k+1) and is met exactly.

A family reaching 2^m would need every subset of a Thompson machine’s states to be reachable, which the construction’s split structure makes impossible — a Thompson machine’s reachable subsets are constrained by its shape.

Which expressions a user writes #

The family here is a witness and the question a system has is whether anything a user writes behaves like it, so it is worth saying what the ingredients are.

The blowup needs an unbounded prefix — .* or (a|b)* — followed by a bounded lookahead: a fixed number of positions whose contents must be remembered.

That is a common shape. .*foo.{10}bar has it. So does any pattern matching “something, then a marker, then a fixed offset”. Log parsing, protocol dissection and data extraction all produce patterns of that form routinely.

What makes the measured family maximal rather than merely bad is that its tail is (a|b), which constrains nothing — so every combination of remembered bits occurs. A tail of literal characters constrains most of them away and the machine is far smaller.

So the realistic version is somewhere between the two lines on the plate, and where depends on how much the tail constrains. A pattern like .*a.{20} on a byte alphabet is close to the bad end; .*abc.{3}xyz is close to the good end.

Nothing here measures a distribution of real patterns, and that is the missing measurement: the family says the worst case is reachable and says nothing about how often.

What this means for a system #

Three things, in order of how directly they follow.

A regular-expression engine cannot bound its deterministic machine’s size from the expression’s length. The bound is exponential and it is met, so any bound has to be a cap with a fallback.

The cap has to be a size rather than a time. A construction that has run for too long has produced a partial table that is useless; one that has produced too many states can stop and fall back to the non-deterministic simulation, which always works.

And the fallback has to exist. An engine whose only machine is deterministic has an expression it cannot compile, and the expression is twenty characters long.

That third is why every real engine has two matchers, and it is a design consequence of a bound rather than an engineering preference.

An exponential nobody calls one #

There is an exponential in a neighbouring structure in this collection and it is worth putting beside this one, because the two are treated very differently.

A backtracking matcher takes exponential time in the text on a fixed expression: (a|a)*b against a run of n a’s costs 2^n steps, which the folklore is about a matcher measures at four million by twenty characters.

That is an exponential in the input rather than in the program, which is much worse — a user cannot avoid it by writing a shorter pattern, only by avoiding the pattern entirely, and a system accepting patterns from users has no defence.

The subset construction’s exponential is in the program, is paid once at construction, and can be capped. So of the two exponentials in this field, the one every engine has is the dangerous one and the one described as pathological is the manageable one.

That the second is the one with a name — “state explosion” — and the first is folklore is an accident of which literature each belongs to.

What the non-deterministic line is doing #

The plate’s lower line is the non-deterministic machine and it is nearly flat compared to the others, which is the whole reason the strand has four machines rather than one.

Thirty states at k = 8, twelve at k = 1, growing by two per operator. Linear, as two states per operator establishes structurally.

So the same expression that produces a five-hundred-state deterministic machine produces a thirty-state non-deterministic one, and the simulation over the second is O(nm) rather than O(n) — a factor of thirty per character, against a construction cost of five hundred states.

Which of those a system should pay is where the table starts paying, and it is a crossing rather than a rule.

Three sizes, one expression #

Ending with the three numbers for one expression at k = 5, because having them together is what the plate is for.

The expression: 21 characters.

The non-deterministic machine: 24 states, built in 24 steps.

The deterministic machine: 64 states, built in 11,297 operations — because building it means running an NFA step for every state and every alphabet symbol.

So the construction’s cost is larger than its output’s size by a factor of a hundred and seventy, which is a thing the state count does not say. Each of the 64 states requires two NFA steps — one per alphabet symbol — and each NFA step is a state-set walk over up to 24 states with closures.

That construction cost is what a lazy machine defers and a cap bounds, and it is the quantity where the table starts paying puts against the text’s length to find a crossing.