Chercher un motif dans un flux est la tâche où le non-déterminisme rend le service le plus visible. L'automate non déterministe s'écrit en trois lignes ; l'automate déterministe équivalent demande de réfléchir à chaque préfixe du motif.
Objectif
Comparer les deux écritures sur la même tâche, et mesurer ce que chacune coûte.
La règle de comptage
Pour un motif de longueur , l'automate déterministe a besoin d'un état par préfixe du motif, du préfixe vide au motif entier, soit états. L'automate non déterministe, lui, en demande toujours aussi, mais sa table s'écrit sans réfléchir : une flèche vers l'avant pour chaque symbole du motif, et une boucle sur l'état initial.
La différence n'est donc pas dans le nombre d'états, elle est dans l'effort d'écriture, et c'est déjà beaucoup.