Wenn NFA und DFA gleichwertig wären, warum hätten wir dann zwei Engines für Regex?

Question

Von Reguläre Ausdrücke 3e:

Als Ergebnis grob gesagt, gibt es drei Arten von regex Motoren:

• DFA (POSIX oder nicht-ähnlich oder so)
• traditioneller NFA (am häufigsten:... Perl, .NET, PHP, Java, Python,)
• POSIX NFA

Aus der Theorie der Berechnung: Formale Sprachen, Automata und Komplexität:

Für jede NFA gibt es einen DFA, die genau die gleiche Sprache akzeptiert.

Kann ich argumentieren, dass NFA und DFA die gleiche Sache sind? Oder auch wenn ihre Fähigkeit, Muster zu erkennen, gleichwertig ist, aber in irgendeiner Weise noch anders ist?

Answer 1

Es gibt zwei Dinge, die Sie fehlen:

1. Die „traditionellen NFA“ Implementierungen tatsächlich Fähigkeiten jenseits der strengen Informatik Definition eines NFA umfassen.

2. Leistungsmerkmale sind eine Selbstverständlichkeit, auch wenn zwei Implementierungen die gleiche Antwort enthalten.

Der Nettoeffekt ist, dass die Backtracking-Implementierungen (Ich mag diesen Namen besser als „traditioneller NFA“) sind etwas ausdrucksvoller als DFA-Implementierungen, weil sie reguläre Ausdrücke wie (\w{3,})\1 entsprechen können, was übereinstimmt drei oder mehr Wortzeichen wiederholt zweimal (etwas, das nicht mit einem DFA abgeglichen werden kann). Gleichzeitig ist für DFA-Implementierungen eine Eingabe-Länge von O (n) garantiert, aber es ist sehr einfach, Regexes mit O (n^2) oder schlechterem Verhalten zu schreiben, wenn ihnen eine Zeichenfolge präsentiert wird, die nicht übereinstimmt. (Siehe https://swtch.com/~rsc/regexp/regexp1.html)