Thompson’s algorithm

Thompson’s algorithm . Algorithm that allows from a regular expression to obtain a non-deterministic finite automaton with empty transitions (AFND-V) equivalent.

Summary

[ hide ]

• 1 Definition
• 2 Example
• 3 See also
• 4 Sources

Definition

Let be a regular expression E, it is traversed according to the order of operational precedence (*,., |) And the groupers to obtain an AFND-V defined by its state diagram according to the steps:

1. The initial state Q0: is placed .
2. If the expression supports the empty string, Q0is indicated as a final state:
3. Each xterminal symbol is represented by a transition .
4. Disjunction (|). Let the expression e ₁ | e _{2 be} the equivalent AFND-V take the form: where T (e ₁ ) and T (e ₂ ) are the AFND-V resulting from the expressions e ₁ and e ₂
5. Concatenation (.). Let the expression e ₁ .e ₂ or more simply e ₁ e ₂ the equivalent AFND-V take the form: where T (e ₁ ) and T (e ₂ ) are the AFND-V resulting from the expressions e ₁ and e ₂ . After concatenation, normally T (e ₁ ) loses its final states to leave only those of T (e ₂ ) .
6. Closing (*). Let the expression e ₁ * be the equivalent AFND-V take the form: where T (e ₁ ) is the AFND-V resulting from the expressions e ₁ .
7. It continues until there are no regular expressions left to convert.

Example

Get a finite automaton equivalent to the regular expression that defines unsigned integers in the Python programming language .

Natural constants or literals in Python are defined by the regular expression:

• 0 | ((1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) *)

The first case is a disjunction that can be outlined as:

Then follows the concatenation ((1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) *) whose representation remains :

It continues momentarily altering the original order, for didactic purposes, the closure and ₂₂ = (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) * :

Then, we continue applying the algorithm to the expressions e ₂₁ = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 and e ₂₂₁ = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 until they are fully reduced.