The exponential is in the expression, and only in some expressions

The exponential is in the expression, and only in some expressions

States against k, for two families. The upper line is the subset DFA of (a|b)*a(a|b)(a|b)(a|b)(a… — 512 states at k = 8, which is 2^(k+1) exactly and not approximately: the machine has to remember which of the last k characters were an a, and every one of those 2^k answers is a distinct set of NFA states. The NFA for the same expression has 30 states and grows by two per operator. The lower line is a literal of the same length, whose DFA has 11 states — one per character. Both families are "a regular expression"; the difference is that one of them asks the machine to remember something and the other does not.

Drawn at 700 × 420, wide on the page. Everything above is what regex-machine returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

6 essays call regex-machine. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.