Algorithmus zur Konvertierung sehr großer NFA in DFA

Ich habe einen wirklich großen nicht deterministischen endlichen Automaten und muss ihn in den DFA konvertieren.

Im Großen und Ganzen meine ich mehr als 40 000 Staaten. Bisher habe ich einige Experimente durchgeführt und den Standardalgorithmus programmiert, der die Tabelle durchsucht (wie hier beschrieben ), aber auch nach der Optimierung ist dies recht langsam und sehr speicherintensiv. Mir ist bewusst, dass die Anzahl der Zustände exponentiell ansteigen kann, aber nach der Minimierung weist der resultierende DFA ungefähr 9.000 Zustände auf, und das ist erträglich.

Meine Frage ist also, gibt es einen Algorithmus, der schneller oder speicherfreundlicher wäre?

Haben Sie den Brzozowski-Algorithmus ausprobiert ? Die Laufzeit im schlimmsten Fall ist exponentiell, aber ich sehe einige Hinweise darauf, dass sie häufig sehr gut funktioniert, insbesondere wenn Sie mit einer NFA beginnen, die Sie in eine DFA konvertieren und minimieren möchten.

Das folgende Papier scheint relevant zu sein:

• Über die Leistung von Automatenminimierungsalgorithmen berichten Marco Almeida, Nelma Moreira und Rogerio Reis.

Es wertet eine Reihe verschiedener Algorithmen für die DFA-Minimierung aus, einschließlich ihrer Anwendung auf Ihre Situation, in der wir mit einer NFA beginnen und diese in eine DFA konvertieren und minimieren möchten.

Wie sieht die Zersetzung der stark verbundenen Komponenten (SCC) Ihres NFA aus (wenn man es als gerichteten Graphen betrachtet)? Enthält es viele Komponenten, bei denen keine der Komponenten zu groß ist? Wenn ja, frage ich mich, ob es möglich sein könnte, einen Divide-and-Conquer-Algorithmus zu entwickeln, bei dem Sie eine einzelne Komponente nehmen, von NFA in DFA konvertieren und dann minimieren und dann das Original durch die neue festgelegte Version ersetzen. Dies sollte für Komponenten mit einem Eintrag möglich sein (wobei alle Kanten in dieser Komponente zu einem einzelnen Scheitelpunkt, dem Eintrittsscheitelpunkt, führen). Ich sehe nicht sofort ein, ob es möglich wäre, so etwas für beliebige NFAs zu tun, aber wenn Sie überprüfen, wie die Struktur des SCC aussieht, können Sie möglicherweise feststellen, ob es sich lohnt, diese Richtung zu erkunden oder nicht .

Dies ist anscheinend kein sehr gut untersuchtes Problem im Sinne bekannter / verfügbarer Algorithmen außer der ursprünglichen / vor langer Zeit verfolgten Strategie "DFA bestimmen / DFA minimieren". Sie scheinen anzugeben, dass der Bestimmungsschritt der problematische ist, aber dies ist natürlich typisch, da er einen Exponentialraum / Zeit-Schlechtfall aufweist. Beachten Sie, dass es mehrere DFA-Minimierungsalgorithmen gibt, deren Leistung im Durchschnitt erheblich variieren kann.

es ist auch informeller als "NFA-Minimierung ohne Bestimmung" bekannt . Es ist bekannt, dass es in dem Sinne schwierig ist, dass es grundsätzlich nicht einmal Approximationsalgorithmen gibt, es sei denn, P = Pspace, wie in diesem Artikel gezeigt:

• Minimierung von NFAs und regulären Ausdrücken von Gregor Gramlich, Georg Schnitger

jedoch hat dieses Papier den im Allgemeinen wenig erforschte bei einigen Algorithmen betrachten, die die determinis DFA 1 auf der Suche nach nicht basieren ^st :

• NFA-Reduktionsalgorithmen durch regelmäßige Ungleichungen Jean-Marc Champarnaud, Fabien Coulon

Wir präsentieren verschiedene Techniken zur Reduzierung der Anzahl von Zuständen und Übergängen in nichtdeterministischen Automaten. Diese Techniken basieren auf den zwei Vorbestellungen über den Satz von Zuständen, die sich auf die Einbeziehung der linken und rechten Sprache beziehen. Da ihre genaue Berechnung NP-schwer ist, konzentrieren wir uns auf Polynomapproximationen, die es ermöglichen, die NFA trotzdem zu reduzieren.

Beachten Sie, dass die AT & T FSM-Bibliothek ein öffentlich verfügbares Paket / eine öffentlich verfügbare Implementierung ist, das / die große NFA / DFA-Konvertierungen / Minimierungen usw. im Allgemeinen so effizient wie möglich handhaben kann .

Es hat eine Strategie, fsmcompactdie manchmal ausreichen kann:

In Fällen, in denen ein Wandler oder ein gewichteter Akzeptor nicht bestimmt werden kann oder sehr groß wird, kann eine andere Optimierung nützlich sein fsmcompact. Diese Operation codiert jedes Dreifache eines Eingabeetiketts, eines Ausgabeetiketts und der Kosten in ein einzelnes neues Etikett, führt eine klassische (ungewichtete Akzeptor-) Bestimmung und Minimierung durch und decodiert dann die codierten Etiketten wieder in ihre ursprünglichen Werte. Dies hat den Vorteil, dass es immer definiert ist und keine Ausgabebezeichnungen oder -kosten entlang von Pfaden verschoben werden. Es hat den Nachteil, dass das Ergebnis weder deterministisch noch minimal sein kann.