Thompson Construction

Difficulty
Average 50%

Thompson Construction

Thompson's algorithm or Thompson's construction makes it possible to construct a automaton non-deterministic with epsilon-transition from a regular expression. The automaton is built recursively from basic patterns:

Unit elements like ∅, ε and a are recognized by

thompson construction

We consider the operators of the regular expression R in decreasing order of exteriority. The outermost operator makes it possible to divide R in R1 | R2, R1.R2 or R1 * which are recognized by

thompson construction

Here is an example of construction with the expression (a | b) (a ∗ | ba ∗ | b ∗) ∗

We start the recursion by creating (A) (B) - the content is only indicative, we will see how to fill A and B as we go.

thompson construction

Then by placing the star on (B) * - here we take the opportunity to do the OR function in (A) = (a | b).

thompson construction

The next step is to do the OR function in (B) = (C | D | E)

thompson construction

The process contained by descending recursively until obtaining the final Thompson automaton.

thompson construction

The latter should then be determined and minimized for better reading.

Some simple examples

  1. 01
  2. (0 + 1)01
  3. 00(0 + 1)*
thompson construction
To share