Algorithmus zur Konvertierung sehr großer NFA in DFA

12

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?

Jendas
quelle
das video ist anscheinend auf dem standardbestimmungsalgorithmus. Siehe z. B. NFA-Minimierung ohne Bestimmung, Stackoverflow
vzn
Wenn Sie die naive NFA-> DFA-Konvertierung (unter Verwendung der Produktkonstruktion) durchführen, wie groß ist der resultierende DFA? (vor der Minimierung)
DW
2
Was möchten Sie mit dem DFA machen? Wenn Sie an Einschlussprüfungen interessiert sind, gibt es Algorithmen, die dies direkt durchführen.
Vijay D
Vielen Dank für sehr schnelle Antworten. Zu der Größe kann ich nicht genau sagen, da mein RAM ausgegangen ist, aber ich werde es näher betrachten und dann die Frage erweitern. Für das, was ich tun möchte, bin ich mir nicht sicher, ob ich darüber offen sprechen kann, da es ein bisschen von meinem festen Know-how ist. Aber ich kann mit Sicherheit feststellen, dass ich den resultierenden DFA tatsächlich brauche.
Jendas
1
Haben Sie versucht, Angluins Algorithmus zum Lernen von DFAs aus Mitgliedschafts- und Äquivalenzabfragen auszuführen? Der Mitgliedschaftsteil ist einfach (führen Sie einfach Ihren DFA für die erforderliche Zeichenfolge aus); Um die Gleichwertigkeit zu gewährleisten, können Sie viele zufällige Zeichenfolgen zeichnen oder alle Zeichenfolgen bis zu einer bestimmten Länge ausprobieren. Dies ist nur eine Heuristik, da Sie nie wirklich wissen werden, wann Sie fertig sind, aber ich habe festgestellt, dass dieser Trick in der Praxis gut funktioniert ...
Aryeh

Antworten:

6

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:

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 .

DW
quelle
Brzozowskis Algorithmus scheint vielversprechend, aber die Divide- und Conquer-Technik noch mehr! In meinem Fall ist dies sehr einfach und erfordert keine großen Codeänderungen. Ich werde das tun und wenn das funktioniert, werde ich Ihre Antwort akzeptieren.
Jendas
2
Ich kam, ich fragte, ich teilte, ich eroberte
Jendas
2

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:

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 :

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.

vzn
quelle
siehe auch NFA-Ermäßigungen Ilie, Navarro, Yu
vzn