Regelmäßiger Ausdruck, der eine DFA mit toten oder überflüssigen Zuständen erzeugt

Question

Ich möchte einen DFA -Minimierer in meinem Lexer implementieren, aber ich kann scheinbar keine DFA produzieren, die nicht so aussieht, als wäre es bereits die minimale DFA für den Ausdruck.

Ich baue die DFA aus einer NFA, die mit Thomson Construction aus einem regelmäßigen Ausdruck nach dem Fix gebaut wird. Es ist ziemlich genau das, was im Drachenbuch beschrieben wird. Um den Lexer zu machen, werden mehrere der NFAs unter Verwendung von Epsilon -Übergängen vom Startzustand kombiniert. Auf dieser kombinierten NFA wird der DFA -Algorithmus angewendet.

Gibt es also einen "bekannten" regelmäßigen Ausdruck, der eine DFA erzeugt, die ein schönes Testbett für die Eliminierung und Minimierung von toter Zustand macht?

Ich könnte natürlich einfach eine seltsame DFA hacken und die Algorithmen darauf anwenden, aber es wäre nicht wirklich ein 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 Informationen genauso wertvoll, seitdem kann ich die Implementierung der staatlichen Eliminierungsfunktion insgesamt überspringen.

Bearbeiten: Falls Sie Implementierungsdetails benötigen, um genau zu beantworten, ist der Code verfügbar Github, spezifisch die NFA.CS und Dfa.cs Klassen. Zusätzlich schrieb ich eine Serie auf Blogeinträge Auf dem Baualgorithmus, den ich verwende, hilft das, wenn das hilft.

Answer 1

OK, also habe ich das auf eine totale Weise herausgefunden. Ich habe ein Werkzeug für die Visualisierung des regulären Ausdrucks erstellt, da ich von meinem Parser eine schöne Debug -Ausgabe erhielt. Dies zeigt treffend einen solchen Ausdruck, dass die Verwendung von Standard -Thompson -Konstruktionstechniken Ihnen eine ziemlich dumme Automata bietet: (a+b+c+)+|abc

Im Tool gezeigt: http://regexvisualizer.apphb.com/?regex=%28a%2BB%2BC%2B%29%2B%7CABC&nfasize=300&dfasize=250#

Dieses Tool führt derzeit eine direkte Thompson -Konstruktion ohne Optimierung durch. Wenn Sie das entfernen |abc Ein Teil des Ausdrucks, der völlig überflüssig ist, sollte der Ausdruck gleich bleiben. Es tut es nicht.