Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Thompson's construction
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, Thompson's construction <a href="/facts/Algorithm/fnl5NmRt">algorithm</a>, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a <a href="/facts/Regular_expression/KFL3veHX">regular expression</a> into an equivalent <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a> (NFA). This NFA can be used to <a href="/facts/Pattern_matching/CEwptMs9">match strings</a> against the regular expression. This algorithm is credited to <a href="/facts/Ken_Thompson/KQtrw9YM">Ken Thompson</a>. </p><p>Regular expressions and nondeterministic finite automata are two representations of <a href="/facts/Formal_language/crDTyP8q">formal languages</a>. For instance, <a href="/facts/Text_processing/5UIbA5za">text processing</a> 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 <a href="/facts/Compiler/WNfCDFJe">compile</a> 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 <a href="/facts/Regular_language/ahxw67T1">regular languages</a>. </p><p>An NFA can be made deterministic by the <a href="/facts/Powerset_construction/FeTghmH7">powerset construction</a> and then be <a href="/facts/DFA_minimization/qASLWje9">minimized</a> to get an optimal automaton corresponding to the given regular expression. However, an NFA may also be <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">interpreted directly</a>. </p><p>To decide whether two given regular expressions describe the same language, each can be converted into an equivalent minimal <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> via Thompson's construction, <a href="/facts/Powerset_construction/FeTghmH7">powerset construction</a>, and <a href="/facts/DFA_minimization/qASLWje9">DFA minimization</a>. If, and only if, the resulting automata agree <a href="/facts/Up_to/ydz4ztzX">up to</a> renaming of states, the regular expressions' languages agree. </p>