Ich möchte einen DFA-Minimierer in meinem Lexer implementieren, aber ich kann nicht scheinen, ein DFA zu erzeugen, das nicht aussieht, als wäre es bereits der minimale DFA für den Ausdruck.
Ich konstruiere das DFA aus einem NFA, das unter Verwendung von Thomson-Konstruktion aus einem regulären Postfix-Ausdruck erstellt wird. Es ist ziemlich genau das, was im Drachenbuch beschrieben wird. Um den Lexer zu erstellen, werden mehrere der NFAs mit Epsilon-Übergängen vom Startzustand kombiniert. Auf diesem kombinierten NFA wird der DFA-Algorithmus angewendet.
Also, gibt es einen "bekannten" regulären Ausdruck, der ein DFA erzeugt, das ein schönes Testbett für die Eliminierung des Todeszustandes und die Minimierung des Zustands bildet?
Ich könnte natürlich einfach ein komisches DFA hacken und die Algorithmen darauf anwenden, aber es wäre wirklich kein richtiger Testfall, oder? Wenn es so ist, dass die Methode, die ich DFAs konstruiere, nicht für tote Zustände anfällig ist, dann wäre diese Information genauso wertvoll, da ich dann die Implementierung der Zustandsbeseitigungsfunktion komplett überspringen kann.
Bearbeiten: Falls Sie Implementierungsdetails benötigen, um genau zu antworten, ist der Code auf github , insbesondere die NFA.cs und DFA.cs Klassen. Zusätzlich schrieb ich eine Reihe auf Blogposts zu dem von mir verwendeten Konstruktionsalgorithmus, wenn das hilft.
Ok, also habe ich das auf Umwegen herausgefunden. Ich habe ein Werkzeug zur Visualisierung von regulärem Ausdruck erstellt, seit ich eine ziemlich gute Debug-Ausgabe von meinem Parser bekommen habe. Dies veranschaulicht treffend einen solchen Ausdruck, dass die Verwendung von Standard-Thompson-Konstruktionstechniken Ihnen einen ziemlich dummen Automaten geben wird: (a+b+c+)+|abc
Im Tool angezeigt: Ссылка
Dieses Werkzeug führt gerade eine Thompson-Konstruktion ohne Optimierung durch. Wenn Sie den Teil |abc des Ausdrucks entfernen, der völlig überflüssig ist, sollte der Ausdruck derselbe bleiben. Tut es nicht.