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

Epsilon closure — where it appears

The set of states a machine can reach without reading a character, computed after every step of a non-deterministic simulation. On Thompson's construction the free transitions point anywhere, so it is a reachability walk over an arbitrary graph rather than a local move.

Named by 2 essays across 2 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 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

Named alongside it

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

AutomatonNondeterministic automatonBit-parallelDeterministic automatonLazy constructionOperation countRegular-expressionState setThompson construction

All concepts