Algorithmus zur Bestimmung, ob zwei reguläre Ausdrücke äquivalent sind

11

Gibt es bei zwei beliebigen regulären Ausdrücken einen "effizienten" Algorithmus, um festzustellen, ob sie mit demselben Satz von Zeichenfolgen übereinstimmen?

Können wir allgemeiner die Größe des Schnittpunkts der beiden Übereinstimmungssätze berechnen?

Welche Algorithmen gibt es dafür und in welcher Komplexitätsklasse leben sie?

Wenn wir den Kleene-Stern nicht zulassen, ändert das überhaupt das Bild?

algorithms regular-expressions MathematicalOrchid
quelle
Was meinst du mit der "Größe der Kreuzung"? In den interessantesten Fällen wird es unendlich groß sein; Interessieren Sie sich für Größen von ? Σn
Raphael
@Raphael Mein Verständnis ist, dass das Eliminieren des Kleene-Sterns die Größe der Menge auf endlich begrenzt.
MathematicalOrchid
Hängt davon ab. Welche anderen Betreiber sind erlaubt? Wenn Sie eine Ergänzung zulassen, ist das, was Sie sagen, nicht wahr. Außerdem fragst du auch nach der Situation mit Kleene Star, also musst du es trotzdem klären.
Raphael
Siehe auch cs.stackexchange.com/q/12624/755
DW

Antworten:

12

Hendrik Jan gibt eine gute Antwort für die Komplexitätsklasse, aber keinen Algorithmus selbst.

Der einfachste Algorithmus, den ich kenne, besteht darin, den regulären Ausdruck in einen DFA zu konvertieren. Es sind Techniken bekannt, um einen regulären Ausdruck in einen NFA und einen NFA in einen DFA umzuwandeln.

Sobald Sie zwei DFAs haben, ist das Testen auf Äquivalenz effizient und entscheidbar, da die Minimalform eines DFA bis zum Isomorphismus eindeutig ist.

Das Erstellen dieser DFAs aus NFAs kann jedoch viel Zeit in Anspruch nehmen und extrem große DFAS erzeugen, die im schlimmsten Fall exponentiell groß sind.

jmite
quelle
10

Es ist bekannt, dass die Gleichwertigkeit regulärer Ausdrücke PSPACE-vollständig ist, was ziemlich schlecht ist. Das Papier "Komplexität von Entscheidungsproblemen für einfache reguläre Ausdrücke" listet mehrere Unterklassen regulärer Ausdrücke mit ihrer jeweiligen Komplexität auf. ( Link )

Hendrik Jan.
quelle
1
e2ee
@dkuper Danke für die zusätzliche Erklärung. Fühlen Sie sich frei, die Antwort zu bearbeiten, um diese oder geeignete Referenzen hinzuzufügen. (Oder starten Sie sogar Ihre eigene Antwort.)
Hendrik
Gibt es eine Referenz für allgemeine reguläre Ausdrücke, die PSPACE-vollständig sind?
Ryan
Dein Link ist tot. Können Sie entweder eine neue oder zumindest einige der relevanten Informationen aus dem Papier bereitstellen?
D. Ben Knoble
@ D.BenKnoble Link funktioniert gut für mich.
Hendrik