La construction de Thompson assemble un automate à partir d'une expression régulière, opération par opération. Chaque brique élémentaire a une entrée et une sortie, ce qui permet de les emboîter sans jamais reprendre ce qui a été construit.
Les trois assemblages
| Opération | Ce que l'assemblage ajoute |
|---|---|
| Concaténation | la sortie de la première brique devient l'entrée de la seconde |
| Union | une entrée commune vers les deux branches, une sortie commune depuis les deux |
| Étoile | un retour de la sortie vers l'entrée, et un chemin qui saute la brique |
Objectif
Compter les états d'un assemblage, sans le dessiner en entier.
Ce que l'étoile ajoute vraiment
Le chemin qui saute la brique est la traduction exacte du « zéro fois ». L'oublier produit un automate qui exige au moins une occurrence, c'est-à-dire un automate qui ne reconnaît pas le même langage que l'expression dont il est censé venir.