Thompson automaton

Thompson’s algorithm allows to build a non-deterministic automaton with epsilon-transition from a regular expression. The automaton is built recursively from basic patterns:

Basic elements like ∅, ε and a are recognized by

langage15

We consider the operators of the regular expression R in descending order of externality. The outermost operator can cut R into R1 | R2, R1.R2 or R1* which are recognized by

langage16

Here is an example of a construct with the expression (a | b) (a * | ba * | b *) *

We start the recursion by the creation of (A) (B) – the content is only indicative, we will see how to fill A and B later.

langage17

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

langage18

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

langage19

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

langage20

The latter will then have to be determinized and minimized for a better reading.

Other examples

  1. 01
  2. (0 + 1)01
  3. 00(0 + 1)*

langage59

 

 

Publicités