Thompson's algorithm

E162099

algorithm automata theory technique construction algorithm

Thompson's algorithm is a classic computer science method for converting regular expressions into nondeterministic finite automata (NFAs), widely used in pattern matching and lexical analysis.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (5)

Label	Occurrences
Thompson construction	2
Thompson NFA construction	1
Thompson's algorithm canonical	1
Thompson's construction	1
Thompson's construction for converting regular expressions to NFAs	1

How this entity was disambiguated

This entity first appeared as the object of triple T1413071 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Thompson's algorithm
Context triple: [Ken Thompson, developed, Thompson's algorithm]

A. Knuth–Morris–Pratt algorithm
The Knuth–Morris–Pratt algorithm is a classic linear-time string-searching algorithm that efficiently finds occurrences of a pattern within a text by precomputing a prefix function to avoid redundant comparisons.
B. Aitken
Aitken is a Scottish-origin surname notably borne by Max Aitken, 1st Baron Beaverbrook, a prominent Canadian-British newspaper magnate and politician.
C. Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
D. Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
E. Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Thompson's algorithm
Target entity description: Thompson's algorithm is a classic computer science method for converting regular expressions into nondeterministic finite automata (NFAs), widely used in pattern matching and lexical analysis.

A. Knuth–Morris–Pratt algorithm
The Knuth–Morris–Pratt algorithm is a classic linear-time string-searching algorithm that efficiently finds occurrences of a pattern within a text by precomputing a prefix function to avoid redundant comparisons.
B. Aitken
Aitken is a Scottish-origin surname notably borne by Max Aitken, 1st Baron Beaverbrook, a prominent Canadian-British newspaper magnate and politician.
C. Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
D. Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
E. Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
F. None of above. chosen

Statements (47)

Predicate	Object
instanceOf	algorithm ⓘ automata theory technique ⓘ construction algorithm ⓘ
abbreviation	Thompson NFA construction ⓘ linked to: Thompson's algorithm
advantage	easy to implement ⓘ guarantees NFA size linear in regex length ⓘ simple and mechanical construction rules ⓘ
alsoKnownAs	Thompson construction ⓘ linked to: Thompson's algorithm
basedOn	regular expressions ⓘ
complexityClass	O(n) in size of regular expression ⓘ
constructs	single accept state NFA ⓘ single start state NFA ⓘ
creator	Ken Thompson ⓘ
field	automata theory ⓘ compiler construction ⓘ computer science ⓘ formal language theory ⓘ lexical analysis ⓘ pattern matching ⓘ
formalizes	semantics of regular expressions via automata ⓘ
guarantees	language equivalence between regex and constructed NFA ⓘ
inputType	regular expression ⓘ
limitation	produces NFAs with epsilon transitions ⓘ
outputType	NFA ⓘ
produces	nondeterministic finite automata ⓘ
property	linear in the length of the regular expression ⓘ systematic construction using small NFA fragments ⓘ
publishedIn	Communications of the ACM ⓘ
relatedTo	Glushkov construction ⓘ position automaton ⓘ powerset construction ⓘ subset construction algorithm ⓘ
supportsOperator	Kleene star ⓘ concatenation ⓘ optional operator ⓘ parentheses grouping ⓘ union ⓘ
taughtIn	compiler design courses ⓘ undergraduate automata theory courses ⓘ
typicalUse	foundation for efficient regex matching implementations ⓘ intermediate step before DFA construction ⓘ
usedIn	compiler front-ends ⓘ lexical analyzers ⓘ pattern matching libraries ⓘ regular expression engines ⓘ
usesTransitionType	epsilon transitions ⓘ
yearIntroduced	1968 ⓘ