Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Nondeterministic automaton — where it appears

A machine that can be in several states at once, so a simulation of it carries a set. Built from a regular expression by Thompson's construction it has two states per operator, and one character costs the set's size rather than one lookup.

Named by 5 essays across 5 fields — each of them below, with the objects they name alongside it.

Thompson's NFA, a set of states43.724 to buildthe subset DFA, built in full1.011,297 to buildthe subset DFA, built on demand41.824 to buildthe state set in machine words37.224 to buildoperations per character; the note is what was paid once, before the first character4,096 characters · k = 643.7 down to 1

What a character costs on four machines

Forty-four operations, one, forty-two, and a number that moves. Four machines for one language, with the construction charged separately from the steps, because a machine that is free per character paid eleven thousand operations before the first one.

machine · Automaton 110100k, the operators after the alternationstatesits DFA: 512its NFA: 30a literal's DFA: 11alphabet ab2^(k+1), exactly

The exponential is in the expression

The subset construction on one family reaches two to the k plus one states, exactly and not approximately. A literal of the same length gives eleven. Both are regular expressions and the difference is that one of them asks the machine to remember something.

bounds · Automaton 0a1b2split3split4a5a6b7split8a9b10split11a12b13split14accept9 character tests · 5 splits · 1 accepting(a|b)*a(a|b)(a|b)(a|b)15 states

Two states per operator

Thompson's construction adds a bounded number of states per rule and no rule copies a sub-machine, so the machine is linear in the expression and is built in linear time. Every exponential in this field is somewhere else.

structures · Automaton 10010³10⁴10³10⁴10⁵characters of textoperations, construction includedcrosses at 256the NFAthe DFA64 DFA statescrosses at 256 characters

Where the table starts paying

Five thousand and sixty-five operations before the first character, then one per character. Against nothing before the first character and thirty-nine per character. They cross at two hundred and fifty-six characters, and that crossing is what an engine's compile decision actually is.

practice · Automaton 1010³10⁴10⁵10⁶characters of textstepsbacktrackingThompson's NFAopen points: capped at4,000,000(a|a)*b12,158x at 20 characters

The folklore is about a matcher

Four million steps against three hundred and twenty-nine, on a twenty-character expression matched against twenty characters. One of the two machines doubles with every character of the input and the other does not, and only one of them is what a regular expression is.

wrong · Automaton

Named alongside it

The objects these essays reach for when they reach for this one.

AutomatonDeterministic automatonRegular-expressionEpsilon closureLazy constructionSubset constructionBacktrackingBit-parallelCrossing pointExponential timeLower boundOperation count

All concepts