À 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.