Thompson's construction

Thompson's construction, also called the McNaughton-Yamada-Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton, or NFA. The resulting NFA can then be used to match strings against the regular expression. The algorithm is credited to Ken Thompson. Text processing utilities describe advanced search patterns with regular expressions, but NFAs are better suited to execution on a computer, so the construction is of practical interest as a way to compile regular expressions into automata. In theory it forms part of the proof that regular expressions and nondeterministic finite automata accept exactly the same languages, the regular languages. An NFA built this way can be made deterministic by the powerset construction and then minimized to an optimal automaton, and two regular expressions describe the same language exactly when their minimal deterministic automata agree up to renaming of states. An NFA may also be interpreted directly without conversion.