Selon le cours, étant donné un motif p, on peut construire un automate et il n'est pas très difficile d'utiliser cet automate pour Voici par exemple l'automate associé au mot coucou.
Utiliser cet automate pour reconnaître si un mot quelconque est égal à coucou n'a pas d'intérêt, mais cet automate se revèle Il s'agit de compiler un motif en un automate non-déterministe,