Algorithme de Thompson

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, l'algorithme de Thompson est un algorithme qui permet, étant donnée une expression régulière, de créer un automate fini qui reconnaît le langage décrit par cette expression. Il est nommé ainsi d'après Ken Thompson qui l'a décrit en 1968[1].

Contexte[modifier | modifier le code]

Le théorème de Kleene affirme que l'ensemble des langages rationnels sur un alphabet est exactement l'ensemble des langages sur reconnaissables par automate fini. Il existe des algorithmes pour passer de l'un à l'autre. L'algorithme de Thompson permet d'aller de l'expression à l'automate, tout comme la construction de Glushkov. L'algorithme de McNaughton et Yamada permet d'aller dans l'autre sens.

Description[modifier | modifier le code]

Principe[modifier | modifier le code]

L'algorithme consiste à construire l'automate peu à peu, en utilisant des constructions standard pour l'union, l'étoile et la concaténation. Ces constructions font apparaître des epsilon transitions qui sont ensuite éliminées[2].

Constructions standards[modifier | modifier le code]

À chaque expression régulière s est associé un automate fini N(s). Cet automate est construit par récurrence sur la structure de l’expression.

Mot vide et mot d'une lettre[modifier | modifier le code]

Le mot vide ε est transformé en :

Thompson-epsilon.svg

La lettre a de l'alphabet est remplacée par :

Thompson-a-symbol.svg

Union[modifier | modifier le code]

L'union de deux expressions (s+t) est remplacée par l'automate suivant, où N(s) et N(t) sont les automates associé à s et t :

inline

Concaténation[modifier | modifier le code]

Pour une concaténation s.t, l'automate est :

inline

Étoile[modifier | modifier le code]

Pour l'étoile de Kleene, s*, l'automate est :

inline

Élimination des epsilon transitions[modifier | modifier le code]

La méthode d'élimination des epsilon transitions est détaillée dans l'article epsilon transition.

Complexité[modifier | modifier le code]

Taille de l'automate[modifier | modifier le code]

On peut donner une majoration de la taille de l’automate en fonction de la taille de l'expression. La taille |e| d'une l'expression e est mesurée par le nombre de symboles qui y figurent, à l'exception des parenthèses. Donc

.

Notons n(s) le nombre d'états de l'automate N(s). Alors

.

Dans tous les cas, on a donc

,

en d'autres termes, le nombre d'états est au plus deux fois la taille de l'expression.

Pour le nombre de transitions, un argument encore plus simple s'applique : de chaque état sortent au plus deux flèches, donc le nombre de transitions est au plus le double du nombre d'états.

Place prise par l'automate[modifier | modifier le code]

Dès la première présentation de l’algorithme, utilisé dans des commande comme grep, l'automate est implémenté par un tableau qui, pour chaque état, contient deux informations : soit ce sont deux numéros d'états, et alors les transitions correspondantes sont des epsilon transitions, soit c'est une lettre et un état, et dans ce cas c'est une transition par une lettre. Cette représentation est très compacte.

Notes et références[modifier | modifier le code]

  1. Thompson 1968.
  2. Jacques Désarménien, « Chapitre 1 : Automates finis », sur Institut d'électronique et d'informatique Gaspard-Monge.

Bibliographie[modifier | modifier le code]

  • Ken Thompson, « Regular expression search algorithm », Comm. Assoc. Comput. Mach., vol. 11,‎ , p. 419–422
  • Robert McNaughton et Hisao Yamada, « Regular expressions and state graphs for automata », IRE Trans. Electronic Computers, vol. EC-9, no 1,‎ , p. 39-47 (DOI 10.1109/TEC.1960.5221603)

Liens externes[modifier | modifier le code]