Incomputer science,Thompson's constructionalgorithm, also called theMcNaughton–Yamada–Thompson algorithm,^[1] is a method of transforming aregular expression into an equivalentnondeterministic finite automaton (NFA).^[2] This NFA can be used tomatch strings against the regular expression. This algorithm is credited toKen Thompson.

Regular expressions and nondeterministic finite automata are two representations offormal languages. For instance,text processing utilities use regular expressions to describe advanced search patterns, but NFAs are better suited for execution on a computer. Hence, this algorithm is of practical interest, since it cancompile regular expressions into NFAs. From a theoretical point of view, this algorithm is a part of the proof that they both accept exactly the same languages, that is, theregular languages.

An NFA can be made deterministic by thepowerset construction and then beminimized to get an optimal automaton corresponding to the given regular expression. However, an NFA may also beinterpreted directly.

To decide whether two given regular expressions describe the same language, each can be converted into an equivalent minimaldeterministic finite automaton via Thompson's construction,powerset construction, andDFA minimization. If, and only if, the resulting automata agreeup to renaming of states, the regular expressions' languages agree.

The algorithm worksrecursively by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules.^[3] More precisely, from a regular expressionE, the obtained automatonA with the transition functionΔ^{[clarification needed]} respects the following properties:

• A has exactly one initial stateq₀, which is not accessible from any other state. That is, for any stateq and any lettera,${\displaystyle \mathrm{\Delta }(q,a)}$ does not containq₀.
• A has exactly one final stateq_f, which is not co-accessible from any other state. That is, for any lettera,${\displaystyle \mathrm{\Delta }(q_f,a)=\mathrm{\varnothing }}$.
• Letc be the number of concatenation of the regular expressionE and lets be the number of symbols apart from parentheses — that is,|,*,a andε. Then, the number of states ofA is2s −c (linear in the size ofE).
• The number of transitions leaving any state is at most two.
• Since an NFA ofm states and at moste transitions from each state can match a string of lengthn in timeO(emn), a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.^{[4][better source needed]}

The following rules are depicted according to Aho et al. (2007),^[1] p. 122. In what follows,N(s) andN(t) are the NFA of the subexpressionss andt, respectively.

Theempty-expression ε is converted to

Asymbola of the input alphabet is converted to

Theunion expressions|t is converted to

Stateq goes via ε either to the initial state ofN(s) orN(t). Their final states become intermediate states of the whole NFA and merge via two ε-transitions into the final state of the NFA.

Theconcatenation expressionst is converted to

The initial state ofN(s) is the initial state of the whole NFA. The final state ofN(s) becomes the initial state ofN(t). The final state ofN(t) is the final state of the whole NFA.

TheKleene star expressions^* is converted to

An ε-transition connects initial and final state of the NFA with the sub-NFAN(s) in between. Another ε-transition from the inner final to the inner initial state ofN(s) allows for repetition of expressions according to the star operator.

• Theparenthesized expression (s) is converted toN(s) itself.

With these rules, using theempty expression andsymbol rules as base cases, it is possible to prove withstructural induction that any regular expression may be converted into an equivalent NFA.^[1]

Two examples are now given, a small informal one with the result, and a bigger with a step by step application of the algorithm.

The picture below shows the result of Thompson's construction on(ε|a*b). The purple oval corresponds toa, the teal oval corresponds toa*, the green oval corresponds tob, the orange oval corresponds toa*b, and the blue oval corresponds toε.

As an example, the picture shows the result of Thompson's construction algorithm on the regular expression(0|(1(01*(00)*0)*1)*)* that denotes the set of binary numbers that are multiples of 3:

{ ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.

The upper right part shows the logical structure (syntax tree) of the expression, with "." denoting concatenation (assumed to have variable arity); subexpressions are nameda-q for reference purposes. The left part shows the nondeterministic finite automaton resulting from Thompson's algorithm, with theentry andexit state of each subexpression colored inmagenta andcyan, respectively.An ε as transition label is omitted for clarity — unlabelled transitions are in fact ε transitions.The entry and exit state corresponding to the root expressionq is the start and accept state of the automaton, respectively.

The algorithm's steps are as follows:

An equivalent minimal deterministic automaton is shown below.

Thompson's is one of several algorithms for constructing NFAs from regular expressions;^[5] an earlier algorithm was given by McNaughton and Yamada.^[6] Converse to Thompson's construction,Kleene's algorithm transforms a finite automaton into a regular expression.

Glushkov's construction algorithm is similar to Thompson's construction, once the ε-transitions are removed.

Regular expressions are often used to specify patterns that software is then asked to match. Generating an NFA by Thompson's construction, and using an appropriate algorithm to simulate it, it is possible to create pattern-matching software with performance that is⁠${\displaystyle O(mn)}$⁠, wherem is the length of the regular expression andn is the length of the string being matched. This is much better than is achieved by many popular programming-language implementations;^[7] however, it is restricted to purely regular expressions and does not supportpatterns for non-regular languages like backreferences.

• Finite-state machines

• CS1 maint: location
• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles needing clarification from February 2021
• All articles lacking reliable references
• Articles lacking reliable references from October 2015