Terminale · Numérique et sciences informatiques

Utiliser un automate fini pour rechercher un motif dans un texte

Construire et exécuter à la main un automate fini déterministe reconnaissant un motif donné, puis l'implémenter en Python pour détecter ses occurrences dans un texte en une seule lecture.

Aperçu gratuit
Illustration de la fiche « Utiliser un automate fini pour rechercher un motif dans un texte »

Les points essentiels

  • Un automate fini déterministe (AFD) est défini par un ensemble d'états, un alphabet, une fonction de transition, un état initial et des états d'acceptation (ici, un seul état final signifiant « motif trouvé »).
  • Pour un motif de longueur m, l'automate de recherche possède m+1 états numérotés de 0 à m : l'état k signifie « les k derniers caractères lus sont exactement le préfixe de longueur k du motif ».

Les mots à connaître

Automate fini déterministe
Machine abstraite à nombre fini d'états qui lit un mot lettre par lettre ; à chaque couple (état, lettre) correspond exactement un état d'arrivée. Elle accepte le mot si elle termine, ou passe, par un état d'acceptation.
Fonction de transition
Application delta qui, à un état et à un caractère lu, associe le nouvel état. Pour la recherche de motif, delta(k, c) est la longueur du plus long préfixe du motif qui est suffixe du mot formé du préfixe de longueur k suivi de c.

Un exemple pour comprendre

Alphabet {a, b}, motif « ab ». Construire l'automate (états 0, 1, 2) puis l'exécuter sur le texte « aabab » en indiquant les positions où le motif est trouvé.

États : 0 (rien), 1 (« a » lu), 2 (« ab » lu, état final). Transitions : delta(0,a)=1 ; delta(0,b)=0 ; delta(1,a)=1 (le mot « aa » a pour plus long suffixe-préfixe « a ») ; delta(1,b)=2 ; delta(2,a)=1 (« aba » finit par « a ») ; delta(2,b)=0 (« abb » ne contient aucun préfixe de « ab » en suffixe). Exécution sur « aabab » (positions 0 à 4) : lecture de a (pos 0) : 0->1 ; a (pos 1) : 1->1 ; b (pos 2) : 1->2 donc motif trouvé, fin en pos 2, début en pos 1 ; a (pos 3) : 2->1 ; b (pos 4) : 1->2 donc motif trouvé, fin en pos 4, début en pos 3. Résultat : « ab » apparaît aux positions 1 et 3.

Première page de l’Essentiel : Utiliser un automate fini pour rechercher un motif dans un texte
Ketty