Un automate non déterministe cherche le motif ab quelque part dans un flux d'événements. Il
n'attend pas le début du motif : il essaie de le commencer à chaque position, et garde toutes les
hypothèses en parallèle.
L'automate
| Depuis | a | b |
|---|---|---|
q0 (initial) | q0, q1 | q0 |
q1 | q2 | |
q2 (acceptant) | q2 | q2 |
Deux transitions partent de q0 avec le symbole a : c'est le signe du non-déterminisme. La
première dit « ce a ne fait pas partie du motif », la seconde dit « ce a commence le motif ».
Objectif
Suivre l'ensemble des états allumés, symbole par symbole, et compter ce qui reste vivant.
Ce qu'un état allumé signifie
Chaque état de l'ensemble est une hypothèse encore possible sur la lecture. L'ensemble se réduit quand des hypothèses meurent, et grandit quand une nouvelle position devient un début de motif plausible. L'automate n'essaie pas les chemins l'un après l'autre : il les tient tous à la fois.