MP/MP*: Option Informatique
Devoir à rendre le jeudi 5 janvier 2006
Une construction de l'automate des sous-mots



Présentation

À partir de l'automate à n+1 états qui reconnaît un mot u de longueur n, il est facile de construire un automate qui reconnaît les sous-mots de u: il suffit d'ajouter une transition instantanée parallèle à chaque transition.

Nous présentons ici un algorithme qui construit un automate fini déterministe (donc sans transitions instantanées) reconnaissant les sous-mots de u.