Datenstruktur zur Darstellung einer DFA

Question

Ich fragte mich, was wäre die beste Datenstruktur, um eine DFA darzustellen.

Ich möchte einen regulären Ausdruck in eine DFA konvertieren und diese besondere Funktionalität als Bibliothek in Java erstellen.

Die Hauptsache ist, dass jede Entität in der Regex eher einen Wert als einen einzelnen String -Wert wie "Auto" trägt. In meinem Fall würde jede Entität viele Eigenschaften wie {Car, Honda, 4x4, Limousine, ...} tragen (obwohl ich nicht nach Autos suche, ist dies nur ein Beispiel.)

Irgendwelche Vorschläge?

Answer 1

Wenn ich Ihre Frage richtig verstehe, möchten Sie eine Matching-/Filterbibliothek für eine willkürliche reguläre Sprache über einem Alphabet mit dynamischen Typen? Wenn Sie sich mit Ihrem Auto -Beispiel vorstellen, möchte ich mir vorstellen, dass Sie einen Ausdruck erstellen können, um über eine Liste zu stimmen, in der alle Autos (die Farbe rot haben, zwischen 2 und 6 Passagieren haben und jeder Passagier zwischen 8 und liegt 88 Jahre alt) oder (haben 1 Passagier).

Zufälligerweise habe ich selbst nach so etwas gesucht (zur Validierung der Dokument Jing; Eine Java Relax-Ng-Bibliothek. Leider besteht das Alphabet in Jing aus XML -Knoten, so dass es mein Problem nicht gelöst hat. Im Moment versuche ich selbst eine Bibliothek zu schreiben, die genau dies tut (die gegen reguläre Sprachen über einem willkürlichen Alphabet -Typ entspricht), basierend auf dem Musterpassungsanpassung im Jing. Wenn Sie dabei helfen möchten, lassen Sie es mich bitte wissen;).

Answer 2

Eine Websuche liefert einige Beispiele für DFAs in Java. Die beste Darstellung hängt jedoch von Ihren spezifischen Anwendungsanforderungen ab. zB wie Ihre Anwendung die DFAs verwenden wird. Ich denke, Sie müssen dies selbst ausarbeiten.

Answer 3

Ich bin mir sicher, dass diese Antwort aufgrund der Daten für die ursprüngliche Frage nicht nützlich sein wird, aber wenn jemand in diesem Bereich von Google passiert ...

DFAs und NFAs können als gespeichert werden Zustandsübergangstabelle, Sie führen dann einen Analyse durch, indem Sie den Nachdenken an die Tabelle bewegten, die den Links als solche folgt.