View source for Thompson's construction

{{Short description|Algorithm to transform a regular expression into a finite automaton}}
In [[computer science]], '''Thompson's construction''' [[algorithm]], also called the '''McNaughton–Yamada–Thompson algorithm''',<ref name="DragonBook">{{cite book |author1=Alfred Vaino Aho |author2=Monica S. Lam |author3=Ravi Sethi |author4=Jeffrey D. Ullman |authorlink1=Alfred Aho |authorlink2=Monica S. Lam |authorlink3=Ravi Sethi |authorlink4=Jeffrey D. Ullman |title=Compilers : Principles, Techniques, & Tools |date=2007 |publisher=Pearson Addison-Wesley |location=Boston, MA, USA |isbn=9780321486813 |page=[https://archive.org/details/compilers00alfr_0/page/159 159–163] |edition=2nd |chapter-url=https://www.pearson.com/us/higher-education/program/Aho-Compilers-Principles-Techniques-and-Tools-2nd-Edition/PGM167067.html |language=en |chapter-format=print |chapter=3.7.4 Construction of an NFA from a Regular Expression |url-access=registration |url=https://archive.org/details/compilers00alfr_0/page/159 }}</ref> is a method of transforming a [[regular expression]] into an equivalent [[nondeterministic finite automaton]] (NFA).<ref>{{cite book |last1=Louden |first1=Kenneth C. |title=Compiler construction : Principles and Practice |date=1997 |publisher=PWS Publishing Company |location=20 Park Plaza Boston, MA 02116-4324, US |isbn=978-0-534-93972-4 |edition=3rd |chapter-url=https://dl.acm.org/citation.cfm?id=523017 |language=en |chapter-format=print |chapter=2.4.1 From a Regular Expression to an NFA |pages=64–69}}</ref> This NFA can be used to [[pattern matching|match strings]] against the regular expression.  This algorithm is credited to [[Ken Thompson]].

Regular expressions and nondeterministic finite automata are two representations of [[formal language]]s.  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 can [[compiler|compile]] 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, the [[regular language]]s.

An NFA can be made deterministic by the [[powerset construction]] and then be [[DFA minimization|minimized]] to get an optimal automaton corresponding to the given regular expression.  However, an NFA may also be [[Nondeterministic finite automaton#Implementation|interpreted directly]].

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

== The algorithm ==

The algorithm works [[recursively]] by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules.<ref>{{cite journal| author=Ken Thompson| title=Programming Techniques: Regular expression search algorithm| journal=Communications of the ACM|date=Jun 1968| volume=11| number=6| pages=419–422| doi=10.1145/363347.363387| s2cid=21260384| doi-access=free}}</ref> More precisely, from a regular expression {{mvar|E}}, the obtained automaton {{mvar|A}} with the transition function {{mvar|Δ}}{{clarification needed|reason=a transition function «math»\Delta«/math» : «math»Q\times\Sigma \rightarrow P(Q)«/math» in the foreign notation of the NFA main article|date=February 2021}} respects the following properties:
* {{mvar|A}} has exactly one initial state {{math|''q''<sub>0</sub>}}, which is not accessible from any other state. That is, for any state {{mvar|q}} and any letter {{mvar|a}}, <math>\Delta(q,a)</math> does not contain {{math|''q''<sub>0</sub>}}.
* {{mvar|A}} has exactly one final state {{mvar|q<sub>f</sub>}}, which is not co-accessible from any other state. That is, for any letter {{mvar|a}}, <math>\Delta(q_f,a)=\emptyset</math>.
* Let {{mvar|c}} be the number of concatenation of the regular expression {{mvar|E}} and let {{mvar|s}} be the number of  symbols apart from parentheses — that is, {{math|{{!}}}}, {{math|*}}, {{mvar|a}} and {{mvar|ε}}. Then, the number of states of {{mvar|A}} is {{math|2''s'' − ''c''}} (linear in the size of {{mvar|E}}).
* The number of transitions leaving any state is at most two.
* Since an NFA of {{mvar|m}} states and at most {{mvar|e}} transitions from each state can match a string of length {{mvar|n}} in time {{math|''O''(''emn'')}}, a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.<ref>{{cite web |first=Guangming |last=Xing |title=Minimized Thompson NFA |url=http://people.wku.edu/guangming.xing/thompsonnfa.pdf}}</ref>{{better source needed|date=October 2015}}

=== Rules ===

The following rules are depicted according to Aho et al. (2007),<ref name=DragonBook /> p.&nbsp;122. In what follows, ''N''({{color|#800000|''s''}}) and ''N''({{color|#008000|''t''}}) are the NFA of the subexpressions {{color|#800000|''s''}} and {{color|#008000|''t''}}, respectively.

The '''empty-expression''' ε is converted to

[[File:Thompson-epsilon.svg|inline]]

A '''symbol''' ''a'' of the input alphabet is converted to

[[File:Thompson-a-symbol.svg|inline]]

The '''union expression''' {{color|#800000|''s''}}|{{color|#008000|''t''}} is converted to

[[File:thompson-or.svg|inline]]

State ''q'' goes via ε either to the initial state of ''N''({{color|#800000|''s''}}) or ''N''({{color|#008000|''t''}}). Their final states become intermediate states of the whole NFA and merge via two ε-transitions into the final state of the NFA.

The '''concatenation expression''' ''st'' is converted to

[[File:thompson-concat.svg|inline]]

The initial state of ''N''({{color|#800000|''s''}}) is the initial state of the whole NFA. The final state of ''N''({{color|#800000|''s''}}) becomes the initial state of ''N''({{color|#008000|''t''}}). The final state of ''N''({{color|#008000|''t''}}) is the final state of the whole NFA.

The '''[[Kleene star]] expression''' {{color|#800000|''s''}}<sup>*</sup> is converted to

[[File:thompson-kleene-star.svg|inline]]

An ε-transition connects initial and final state of the NFA with the sub-NFA ''N''({{color|#800000|''s''}}) in between. Another ε-transition from the inner final to the inner initial state of ''N''({{color|#800000|''s''}}) allows for repetition of expression {{color|#800000|''s''}} according to the star operator.

* The '''parenthesized expression''' ({{color|#800000|''s''}}) is converted to ''N''({{color|#800000|''s''}}) itself.

With these rules, using the '''empty expression''' and '''symbol''' rules as base cases, it is possible to prove with [[structural induction]] that any regular expression may be converted into an equivalent NFA.<ref name="DragonBook" />

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

===Small Example===
[[File:Small-thompson-example.svg|thumb|444px|Example of {{code|(ε{{!}}a*b)}} using Thompson's construction, step by step]]
The picture below shows the result of Thompson's construction on <code>(ε|a*b)</code>. The purple oval corresponds to ''a'', the teal oval corresponds to ''a*'', the green oval corresponds to ''b'', the orange oval corresponds to ''a*b'', and the blue oval corresponds to ''ε''.

===Application of the algorithm===
[[File:Thompson's construction algorithm applied to regular expression for binary multiples of 3.gif|thumb|494px|NFA obtained from regular expression <code><nowiki>(0|(1(01*(00)*0)*1)*)*</nowiki></code>]]

As an example, the picture shows the result of Thompson's construction algorithm on the regular expression {{Nowrap begin}}<code>(0|(1(01*(00)*0)*1)*)*</code>{{Nowrap end}} 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 named {{color|#c0c000|a}}-{{color|#c0c000|q}} for reference purposes. 
The left part shows the nondeterministic finite automaton resulting from Thompson's algorithm, with the {{color|#c000c0|entry}} and {{color|#00c0c0|exit}} state of each subexpression colored in {{color|#c000c0|magenta}} and {{color|#00c0c0|cyan}}, respectively.
An ε as transition label is omitted for clarity &mdash; unlabelled transitions are in fact ε transitions.
The entry and exit state corresponding to the root expression {{color|#c0c000|q}} is the start and accept state of the automaton, respectively.

The algorithm's steps are as follows:
{| 
|-
| ''q'': || colspan=9 | start converting Kleene star expression                           || <code><nowiki>(0|(1(01*(00)*0)*1)*)*</nowiki></code>
|-
| || ''b'': || colspan=8 | start converting union expression                              || <code><nowiki>0|(1(01*(00)*0)*1)*</nowiki></code>
|- 
| || || ''a'': || colspan=7 | convert symbol                                              || <code>0</code>
|- 
| || || ''p'': || colspan=7 | start converting Kleene star expression                     || <code>(1(01*(00)*0)*1)*</code>
|- 
| || || || ''d'': || colspan=6 | start converting concatenation expression                || <code>1(01*(00)*0)*1</code>
|- 
| || || || || ''c'': || colspan=5 | convert symbol                                        || <code>1</code>
|- 
| || || || || ''n'': || colspan=5 | start converting Kleene star expression               || <code>(01*(00)*0)*</code>
|- 
| || || || || || ''f'': || colspan=4 | start converting concatenation expression          || <code>01*(00)*0</code>
|- 
| || || || || || || ''e'': || colspan=3 | convert symbol                                  || <code>0</code>
|- 
| || || || || || || ''h'': || colspan=3 | start converting Kleene star expression         || <code>1*</code>
|- 
| || || || || || || || ''g'': || colspan=2 | convert symbol                               || <code>1</code>
|- 
| || || || || || || ''h'': || colspan=3 | finished converting Kleene star expression      || <code>1*</code>
|- 
| || || || || || || ''l'': || colspan=3 | start converting Kleene star expression         || <code>(00)*</code>
|- 
| || || || || || || || ''j'': || colspan=2 | start converting concatenation expression    || <code>00</code>
|- 
| || || || || || || || || ''i'': || colspan=1 | convert symbol                            || <code>0</code>
|- 
| || || || || || || || || ''k'': || colspan=1 | convert symbol                            || <code>0</code>
|- 
| || || || || || || || ''j'': || colspan=2 class="nowrap"|finished converting concatenation expression || <code>00</code>
|- 
| || || || || || || ''l'': || colspan=3 |finished converting Kleene star expression      || <code>(00)*</code>
|- 
| || || || || || || ''m'': || colspan=3 |convert symbol                                  || <code>0</code>
|- 
| || || || || || ''f'': || colspan=4 |finished converting concatenation expression       || <code>01*(00)*0</code>
|- 
| || || || || ''n'': || colspan=5 |finished converting Kleene star expression            || <code>(01*(00)*0)*</code>
|- 
| || || || || ''o'': || colspan=5 |convert symbol                                        || <code>1</code>
|- 
| || || || ''d'': || colspan=6 |finished converting concatenation expression             || <code>1(01*(00)*0)*1</code>
|- 
| || || ''p'': || colspan=7 |finished converting Kleene star expression                  || <code>(1(01*(00)*0)*1)*</code>
|- 
| || ''b'': || colspan=8 |finished converting union expression                           || <code><nowiki>0|(1(01*(00)*0)*1)*</nowiki></code>
|-
| ''q'': || colspan=9 |finished converting Kleene star expression                        || <code><nowiki>(0|(1(01*(00)*0)*1)*)*</nowiki></code>
|}

An equivalent minimal deterministic automaton is shown below.

[[File:DFA example multiplies of 3.svg|369px|center]]

==Relation to other algorithms==
Thompson's is one of several algorithms for constructing NFAs from regular expressions;<ref>{{cite tech report |first=Bruce W. |last=Watson |title=A taxonomy of finite automata construction algorithms |institution=[[Eindhoven University of Technology]] |number=Computing Science Report 93/43 |year=1995 |url=http://alexandria.tue.nl/extra1/wskrap/publichtml/9313452.pdf}}</ref> an earlier algorithm was given by McNaughton and Yamada.<ref>{{cite journal| author=R. McNaughton, H. Yamada| title=Regular Expressions and State Graphs for Automata| journal=IEEE Transactions on Electronic Computers|date=Mar 1960| volume=9| number=1| pages=39–47| doi=10.1109/TEC.1960.5221603 }}</ref> 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.

==Use in string pattern matching==

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 {{tmath|O(mn)}}, where ''m'' is the length of the regular expression and ''n'' is the length of the string being matched. This is much better than is achieved by many popular programming-language implementations;<ref>{{cite web |last1=Cox |first1=Russ |title=Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) |url=https://swtch.com/~rsc/regexp/regexp1.html |website=swtchboard |access-date=25 February 2025}}</ref> however, it is restricted to purely regular expressions and does not support [[Regular_expression#Patterns_for_non-regular_languages|patterns for non-regular languages]] like backreferences.

==References==
{{reflist}}

{{Strings |state=collapsed}}

[[Category:Finite automata]]