Gibt es eine Möglichkeit herauszufinden, ob zwei beliebige reguläre Ausdrücke äquivalent sind? Sieht für mich wie ein komplexes Problem aus, aber vielleicht gibt es einen DFA-Vereinfachungsmechanismus oder so etwas?Reguläre Ausdrücke Äquivalenz
Äquivalenz testen Sie die minimal DFAs für die Ausdrücke berechnen kann, und vergleichen sie .
Diese beiden PerlMonks Themen diskutieren diese Frage (insbesondere blokhead Antworten lesen):
Testbarkeit der Gleichheit ist eine der klassischen Eigenschaften von regulären Ausdrücken. (NB Dies gilt nicht, wenn Sie wirklich reden Perl reguläre Ausdrücke oder einem anderen technisch irreguläre superlanguage.)
Ihre REs zu verallgemeinern endlichen Automaten A drehen und B, bauen dann einen neuen Automaten AB, so dass die akzeptierenden Zustände von A haben Null-Übergänge zu den Anfangszuständen von B, und die akzeptierenden Zustände von B sind invertiert. Dadurch erhalten Sie einen Automaten, der alle von A akzeptierten Strings akzeptiert, mit Ausnahme aller von B akzeptierten Strings.
Tun Sie dasselbe für B-A und reduzieren Sie beide auf reine FAs. Wenn ein FA keine akzeptierenden Zustände hat, auf die von einem Startzustand aus zugegriffen werden kann, akzeptiert er die leere Sprache. Wenn Sie zeigen können, dass sowohl AB als auch BA leer sind, haben Sie gezeigt, dass A = B ist.
Edit Heh, ich kann nicht glauben, dass niemand den gigantischen Fehler dort bemerkt hat - eine absichtliche, natürlich: - p
Die Automaten AB wie beschrieben akzeptieren diejenigen Strings, deren erste Hälfte von A akzeptiert wird und deren zweite Hälfte von B nicht akzeptiert wird. Der gewünschte AB ist ein etwas komplizierterer Prozess. Ich kann mir das nicht von ganzem Herzen vorstellen, aber ich weiß, dass es wohldefiniert ist (und wahrscheinlich auch die Schaffung von Zuständen für die Repräsentation der Produkte von akzeptierenden Staaten in A und nicht akzeptierenden Staaten in B).
Für A-B möchten Sie stattdessen Schnittpunkt und Komplement verwenden, was in Regex-Bibliotheken leider nicht üblich ist, obwohl sie für "echte" Regexes implementiert werden können (anstelle der Perl-Art). (Weder testen, wenn eine Regex nichts akzeptiert. Bibliotheken sind scheiße, nicht wahr?) –
Das hängt wirklich davon ab, was Sie mit regulären Ausdrücken meinen. Wie die anderen Poster zeigen, sollte die Reduzierung beider Ausdrücke auf ihre minimale DFA funktionieren, aber sie funktioniert nur für die reinen regulären Ausdrücke.
Einige der Konstrukte, die in den Regex-Bibliotheken der realen Welt verwendet werden (insbesondere Rückreferenzen), geben ihnen die Möglichkeit, Sprachen auszudrücken, die nicht regulär sind. Daher funktioniert der DFA-Algorithmus nicht. Zum Beispiel entspricht die Regex: ([a-z]*) \1 einem doppelten Vorkommen desselben Wortes, das durch ein Leerzeichen getrennt ist (a a und b b, aber nicht b a noch a b). Dies kann von einem endlichen Automaten überhaupt nicht erkannt werden.
Was meinen Sie mit dem Vergleich zweier DFAs? Graph Isomorphie? – damned
Da Sie einen Anfangszustand haben und die Übergänge markiert und deterministisch sind, ist es einfach, DFAs auf Gleichheit zu prüfen, viel einfacher als Graphisomorphismus. Ein Tiefendurchlauf sollte ausreichen. – starblue
@starblue Toller Link! – Mooncrater