Moteurs DFA vs NFA: Quelle est la différence dans leurs capacités et limites?

Voici une réponse non technique de Microsoft:

les moteurs DFA fonctionnent en temps linéaire parce qu'ils ne nécessitent pas de traçage arrière (et donc ils ne testent jamais le même caractère deux fois). Ils peuvent également garantir la correspondance avec la chaîne la plus longue possible. Cependant, comme un moteur DFA ne contient que des états finis, il ne peut pas correspondre à un motif avec des références arrières, et parce qu'il ne construit pas d'expansion explicite, il ne peut pas capturer de sous-expressions.

Les moteurs NFA traditionnels exécutent des algorithmes de rétrotractage de match dits" cupides", testant toutes les extensions possibles d'une expression régulière dans un ordre spécifique et acceptant le premier match. Parce qu'un NFA traditionnel construit une extension spécifique de l'expression régulière pour une correspondance réussie, il peut capturer des correspondances sous-expressives et des rétroréférences correspondantes. Cependant, parce qu'un retour en arrière traditionnel NFA, il peut visiter exactement le même état plusieurs fois si l'état est arrivé à plus de différents chemin. En conséquence, il peut courir exponentiellement lentement dans le pire des cas. Parce qu'une NFA traditionnelle accepte le premier match qu'elle trouve, elle peut aussi laisser d'autres matches (peut-être plus longs) non découverts.

POSIX NFA sont comme les moteurs traditionnels NFA, sauf qu'ils continuent à faire marche arrière jusqu'à ce qu'ils puissent garantir qu'ils ont trouvé la plus longue correspondance possible. En conséquence, un moteur POSIX NFA est plus lent qu'un moteur NFA traditionnel, et lorsque vous utilisez un moteur POSIX NFA vous ne pouvez pas favorisez un match plus court qu'un match plus long en changeant l'ordre de la recherche de backtracking.

Les moteurs traditionnels NFA sont favorisés par les programmeurs parce qu'ils sont plus expressifs que les moteurs DFA ou POSIX NFA. Bien que dans le pire des cas ils puissent courir lentement, vous pouvez les orienter pour trouver des correspondances dans le temps linéaire ou polynomial en utilisant des modèles qui réduisent les ambiguïtés et limitent le backtracking.

[http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx]

Un simple, non technique, de l'explication, de reformulation de Jeffrey Friedl du livre Mastering Regular Expressions .

mise en garde :

bien que ce livre soit généralement considéré comme la "bible regex", il semble y avoir une certaine controverse quant à savoir si la distinction faite ici entre DFA et NFA est réellement correcte. Je ne suis pas un informaticien, et je ne comprends pas la plupart de la théorie est vraiment une expression" régulière", déterministe ou non. Après le début de la controverse, j'ai supprimé cette réponse à cause de cela, mais depuis lors elle a été référencée dans les commentaires à d'autres réponses. Je serais très intéressé d'en discuter plus - se peut-il que Friedl est vraiment mauvais? Ou je me suis trompé de friture (mais j'ai relu ce chapitre hier soir, et c'est comme dans mes souvenirs...)?

Edit: il semble que Friedl et moi sommes en effet mauvais. Veuillez consulter les excellents commentaires d'Eamon ci-dessous.

réponse originale:

UN DFA moteur étapes à travers la chaîne d'entrée caractère par caractère et tente (et de mémoire) toutes les voies possibles pour l'expression rationnelle pourrait correspondre à ce point. Si elle atteint la fin de la chaîne, il déclare succès.

Imagine la chaîne AAB et le regex A*AB . Nous passons maintenant à travers notre string lettre par lettre.

1. A :

   • Première branche: Peut être mis en correspondance par A* .
   • deuxième branche: peut être comparée en ignorant le A* (aucune répétition est permise) et en utilisant le deuxième A dans le regex.

2. A :

   • Première branche: Peut être compensée par l'expansion de A* .
   • deuxième branche: ne correspond pas à B . Deuxième branche échoue. Mais:
   • Troisième branche: Peut être compensée par ne pas étendre A* et le second A à la place.

3. B :

   • premier branche: il n'est pas possible de trouver la correspondance en étendant A* ou en passant dans la regex au jeton suivant A . Première branche échoue.
   • troisième branche: peut être jumelée. Hourra!

UN DFA moteur jamais revient dans la chaîne.

Un NFA moteur étapes à travers la regex jeton par jeton et tente le tout pour permutations possibles sur la chaîne, retour en arrière si nécessaire. Si elle atteint la fin de la regex, il déclare succès.

Imaginez la même chaîne et le même regex qu'avant. Nous passons maintenant à travers notre jeton regex par jeton:

1. A* : Match AA . Rappelez-vous les positions 0 (début de la chaîne) et 1.
2. A : ne correspond pas. Mais nous avons une position de retour en arrière que nous pouvons retourner et essayer de nouveau. Le moteur regex recule d'un caractère. Maintenant A correspond.
3. B : les Matchs. Fin de regex atteinte (avec une position de backtracking de rechange). Hourra!

NFA et DFAs sont des automates finis, comme leurs noms le disent.

les deux peuvent être représentés comme un État de départ, un État de succès (ou un ensemble d'états de succès), et une table d'état énumérant les transitions.

dans la table d'état D'un DFA, chaque clé <state₀, input> passera à une seule clé state₁ .

dans le tableau d'état d'un NFA, chaque <state₀, input> passera à un ensemble de Unis.

quand vous prenez un DFA, réinitialisez-le à son état de départ, une séquence de symboles d'entrée, et vous savez exactement dans quel état de fin il est et si c'est un État de succès ou non.

quand vous prenez un NFA, cependant, il va, pour chaque symbole d'entrée, regarder l'ensemble des états de résultat possibles, et (en théorie) au hasard, non déterministe, choisir l'un d'eux. S'il existe un ensemble de sélections aléatoires qui conduit à l'un des états de succès pour cela chaîne d'entrée, puis le TFD est dit pour réussir la chaîne. En d'autres termes, on s'attend à prétendre que la magie sélectionne toujours la bonne.

une des premières questions en informatique était de savoir si les NFA étaient plus puissants que les DFAs, en raison de cette magie, et la réponse s'est avérée être Non puisque n'importe quelle NFA pourrait être traduit dans un Dfa équivalent. leurs capacités et leurs limites sont exactement les mêmes.

je trouve l'explication donnée dans expressions régulières, le tutoriel complet de Jan Goyvaerts pour être le plus utilisable. Voir page 7 de ce PDF:

https://www.princeton.edu/~mlovett/reference / Regular-Expressions.pdf

parmi les autres points mentionnés à la page 7, il y a deux types de moteurs à expression régulière: les moteurs à direction textuelle et les moteurs à direction regex. Jeffrey Friedl appelle les moteurs DFA et NFA, respectivement. ...certaines caractéristiques très utiles, telles que les quantificateurs paresseux et les rétroréférences, ne peuvent être mises en œuvre que dans les moteurs régex-directed.