Gibt es "kleine" Maschinen, die effizient mit regulären Ausdrücken übereinstimmen können?

Es ist bekannt, dass ein regulärer Ausdruck durch einen nicht deterministischen endlichen Automaten mit einer Größe proportional zum regulären Ausdruck oder durch einen deterministischen FA erkannt werden kann, der potenziell exponentiell größer ist. Darüber hinaus kann die NFA mit einem String und einem regulären Ausdruck r die Mitgliedschaft in einer Zeit testen, die proportional zu | ist s | ⋅ | r | und das DFA kann die Mitgliedschaft in einer Zeit testen, die proportional zu | ist s $s$$r$$|s| \cdot |r|$$|s|$. Die Verlangsamung für die NFA ergibt sich aus der Tatsache, dass wir im Wesentlichen die Mengen möglicher Zustände verfolgen müssen, in denen sich der Automat befinden könnte, und die exponentielle Explosion für die DFA ergibt sich aus der Tatsache, dass ihre Zustände Elemente des Potenzsatzes der Zustände der NFA.

Ist es möglich, reguläre Ausdrücke effizient (dh zeitlich besser als und räumlich besser als O ( 2 | r | ) ) zu erkennen, wenn leistungsfähigere Maschinen als endliche Automaten verwendet werden dürfen? (Gibt es zum Beispiel Prägnanzgewinne beim Erkennen regulärer Sprachen mit Pushdown-Automaten oder Zählmaschinen?)$O(|r| \cdot |s|)$$O(2^{|r|})$

Es ist einfach genug, Zeit gegen Raum zu tauschen, wie folgt.

Konvertieren Sie den regulären Ausdruck in einen NFA. Um den Vergleich von Algorithmen zu verdeutlichen, nehmen wir an, dass die Anzahl der NFA-Zustände ist, sodass Ihre O ( r s ) -Zeit für die direkte Simulation des NFA gültig ist und Ihr O ( 2 r) ) Der für die Ausführung des konvertierten DFA gebundene Speicherplatz ist auch gültig, wenn Sie in einem RAM arbeiten, der so viel Speicher adressieren kann.$r$$O(rs)$$O(2^r)$

Teilen Sie nun die Zustände der NFA (beliebig) in Teilmengen S i von jeweils höchstens ⌈ r / k ⌉ Zuständen auf. Innerhalb jeder Teilmenge S i , wir können Indexuntermengen A i von S i durch Zahlen von 0 zu 2 ⌈ r / k ⌉ - 1 .$k$$S_i$$\lceil r/k\rceil$$S_i$$A_i$$S_i$$0$$2^{\lceil r/k\rceil}-1$

Erstellen Sie eine Tabelle wobei i und j im Bereich von 0 bis k - 1 liegen , c ein Eingabesymbol ist und A i (der numerische Index von) eine Teilmenge von S i ist . Der in der Tabelle gespeicherte Wert ist (der numerische Index von) eine Teilmenge von S j : Ein Zustand y ist genau dann in T [ i , j , c , A i ], wenn$T[i,j,c,A_i]$$i$$j$$k-1$$c$$A_i$$S_i$$S_j$$y$$T[i,j,c,A_i]$ gehört zu S j und es gibt einen Zustand in A i , derbeim Eingabesymbol c zu y übergeht .$y$$S_j$$A_i$$y$$c$

Um die NFA zu simulieren, pflegen Sie Indizes, einen für jedes S i , und geben Sie die Teilmenge A i der Zustände in S i an , die durch ein Präfix der Eingabe erreicht werden können. Verwenden Sie für jedes Eingabesymbol c die Tabellen, um für jedes Paar i , j die Menge von Zuständen in S j nachzuschlagen , die von einem Zustand in A i durch einen Übergang auf c erreicht werden können , und verwenden Sie dann ein bitweises binäres oder Operation an den numerischen Indizes dieser Mengen von Zuständen, um sie zu einer einzigen Teilmenge von Zuständen von S j zu kombinieren$k$$S_i$$A_i$$S_i$$c$$i,j$$S_j$$A_i$$c$$S_j$. Jeder Schritt der Simulation benötigt also die Zeit , und die Gesamtzeit für die Simulation beträgt O ( s k 2 ) .$O(k^2)$$O(sk^2)$

Der benötigte Platz ist der Platz für alle Tabellen, der . Die Zeit- und Raumanalyse gilt für jeden RAM, der so viel Speicher adressieren kann, und für binäre Operationen für Wörter, die groß genug sind, um so viel Speicher zu adressieren.$O(k^2 2^{r/k})$

Der Zeit-Raum-Kompromiss, der sich daraus ergibt, passt aufgrund der quadratischen Abhängigkeit von nicht perfekt zur NFA-Simulation . Aber dann, ich bin skeptisch , dass O ( r s ) ist der richtige Zeitpunkt für die Simulation NFA gebunden: wie Sie einen einzelnen Schritt des NFA simulieren kann schneller als bei allen suchen die (möglicherweise quadratisch viele) von einem zur Zeit erlaubten Übergänge aktiver Zustand in einen anderen Zustand? Sollte es nicht O ( r 2 s ) sein ?$k$$O(rs)$$O(r^2 s)$

Indem Sie variieren lassen, können Sie auf jeden Fall Zeitgrenzen für ein Kontinuum zwischen den DFA- und NFA-Grenzen erhalten, mit weniger Platz als der DFA.$k$

Dies ist keine Antwort, aber zu lang für einen Kommentar. Ich versuche zu erklären, warum die gestellte Frage möglicherweise schwer zu verstehen ist.

Es gibt zwei Möglichkeiten, den Rechenaufwand für ein Gerät X zu definieren .

Der erste und natürlichste Weg ist intrinsisch . Man muss sagen, wie das Gerät X die Eingabe verwendet, damit wir später untersuchen können, wie sich die Größe n der Eingabe auf die Laufzeit des Geräts auswirkt. Man muss auch sagen, was als Operation (oder Schritt ) zählt. Dann lassen wir das Gerät einfach für die Eingabe- und Zähloperationen laufen.

Der zweite ist extrinsisch . Wir definieren Rechenaufwand für ein anderes Gerät Y und wir dann programmieren Y als Simulator zur handeln X . Da es für Y mehrere Möglichkeiten geben kann, X zu simulieren , müssen wir hinzufügen, dass wir die beste verwenden sollen. Lassen Sie mich sagen , das gleiche mit anderen Worten: Wir sagen , dass X nimmt Zeit auf einer Eingabe der Größe n , wenn es einen Simulator existiert X auf Maschine implementiert Y das dauert f ( n ) Zeit.$O(f(n))$$f(n)$

Beispielsweise besagt eine intrinsische Definition für NFA, dass es n Schritte dauert , um eine Zeichenfolge der Länge n zu verarbeiten . Eine extrinsische Definition, die eine RAM-Maschine als Gerät Y verwendet, besagt, dass die bekannteste Obergrenze wahrscheinlich die ist, auf die David Eppstein geantwortet hat. (Andernfalls wäre es seltsam, dass (1) die beste praktische Implementierung, auf die in der anderen Antwort hingewiesen wird, nicht die bessere Alternative verwendet und (2) hier niemand eine bessere Alternative angegeben hat.) Beachten Sie auch, dass genau genommen Ihr Gerät X der reguläre Ausdruck ist Da der NFA jedoch dieselbe Größe hat, ist es sicher, ihn als das betrachtete Gerät X zu betrachten.

Wenn Sie nun die zweite Art von Definition verwenden, ist es wenig sinnvoll zu fragen, wie sich die Einschränkung der Funktionen von Gerät X auf die Laufzeit auswirkt. Es ist jedoch sinnvoll zu fragen, wie sich die Einschränkung der Funktionen von Gerät Y auf die Laufzeit auswirkt. Offensichtlich, so dass leistungsfähigere Maschinen Y könnte es uns ermöglichen , zu simulieren X schneller. Wenn wir also von einer der leistungsstärksten Maschinen ausgehen, die implementiert werden könnten (dies schließt beispielsweise nicht deterministische Maschinen aus), und eine untere Schranke vorgeben , dann wissen wir, dass keine weniger leistungsfähige Maschine dies kann besser.$\Omega(f(n))$

In gewisser Hinsicht ist die beste Antwort, auf die Sie hoffen können, ein Beweis in etwas wie dem Zellsondenmodell, dass die Simulation eines NFA eine gewisse Zeit benötigt. (Beachten Sie, dass Sie, wenn Sie die Konvertierung von NFA in DFA berücksichtigen, Zeit benötigen, um den großen DFA aufzuschreiben, damit nicht nur der Arbeitsspeicher in Frage kommt.)

Auch wenn Sie der Meinung sind, dass es nichts Neues oder Altes gibt, was man über das Matching von regulären Ausdrücken lernen kann, lesen Sie eine der schönsten Arbeiten, die mir seit langem begegnet sind: Ein Stück über reguläre Ausdrücke von S Fischer, F Huch und T Wilke, ICFP 2010.

(MMT Chakravarty verdient die Anerkennung für die Empfehlung dieses Papiers.)

EDIT: Der Grund, warum dieses Papier relevant ist, ist, dass es eine neue Technik (basierend auf Glushkovs aus den 60er Jahren) beschreibt, die es vermeidet, die vollständige NFA (geschweige denn die DFA) zu konstruieren, die der RE entspricht. Was stattdessen getan wird, ähnelt dem Ausführen eines Markierungsalgorithmus, der dem bekannten Algorithmus zur Entscheidung über die Annahme eines Wortes durch eine NFA im Syntaxbaum der RE ähnlich ist. Leistungsmessungen deuten darauf hin, dass dies trotz der kürzlich veröffentlichten re2-Bibliothek von Google wettbewerbsfähig ist.

Schauen Sie sich diesen Artikel von Russ Cox an. Es beschreibt einen NFA-basierten Ansatz, der zuerst von Ken Thompson angewendet wurde und mit dem eine Eingabezeichenfolge s mit einem regulären Ausdruck r in der Zeit O (| s |. C ) und dem Raum O (| r |. D ) abgeglichen werden kann , wobei c und d sind Konstanten der oberen Grenze. Der Artikel beschreibt auch eine C-Implementierung der Technik.