Thompson's construction

For instance, text processing utilities use regular expressions to describe advanced search patterns, but NFAs are better suited for execution on a computer.

An NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression.

The algorithm works recursively 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 expression E, the obtained automaton A with the transition function Δ[clarification needed] respects the following properties: The following rules are depicted according to Aho et al. (2007),[1] p. 122.

denoting concatenation (assumed to have variable arity); subexpressions are named a-q for reference purposes.

The left part shows the nondeterministic finite automaton resulting from Thompson's algorithm, with the entry and exit state of each subexpression colored in magenta and cyan, respectively.

[6] Converse to Thompson's construction, Kleene's algorithm transforms a finite automaton into a regular expression.