Reguläre Ausdrücke, Äquivalenz

Ist es ein Weg, um herauszufinden, ob zwei beliebige reguläre Ausdrücke sind äquivalent? Sieht aus wie Komplexes problem für mich, aber es könnte einige DFA-Vereinfachung Mechanismus oder so?

InformationsquelleAutor amit | 2009-02-18
  1. 10

    Zur Prüfung der Gleichwertigkeit können Sie berechnen die minimale DFAs für die Ausdrücke und Vergleiche Sie.

    • was meinst du mit Vergleich von zwei DFAs? Graph-Isomorphismus?
    • Da haben Sie einen Anfangszustand und übergänge gekennzeichnet sind deterministische und es ist leicht zu überprüfen, DFAs für Gleichheit, viel einfacher als graph-Isomorphismus. Eine tiefenprüfung sollte ausreichen.
    • Toller link!
    InformationsquelleAutor starblue
  2. 10

    Testbarkeit der Gleichheit ist eine der klassischen Eigenschaften von regulären Ausdrücken. (N. B. Diese nicht zu halten, wenn Sie wirklich reden reguläre Perl-Ausdrücke oder eine andere technisch nichtreguläres superlanguage.)

    Schalten Sie Ihre REs zu verallgemeinerten endlichen Automaten A und B, dann konstruieren Sie einen neuen Automaten A-B so, dass die akzeptierenden Zustände von null-Transitionen auf die start-Staaten von B ist, und dass die Annahme von Zuständen von B invertiert sind. Damit erhalten Sie einen Automaten, der akzeptiert alle diese Zeichenfolgen akzeptiert, mit Ausnahme für alle diejenigen, die akzeptiert von B.

    Tun das gleiche für B-A, und reduzieren sowohl die reinen FAs. Wenn ein FA hat keine Annahme von Staaten, die über einen start-Zustand, dann ist es die leere Sprache akzeptiert. Wenn man zeigen kann, dass sowohl A-B und B-A sind leer, Sie haben gezeigt, dass A = B.

    Edit Heh, ich kann nicht glauben, dass niemand bemerkt, die riesigen Fehler -- eine absichtliche, natürlich :-p

    Des Automaten A-B, wie beschrieben, akzeptieren Sie diese Zeichenfolgen, dessen erste Hälfte wird akzeptiert von A und deren zweite Hälfte wird nicht akzeptiert von B. Aufbau der gewünschte A-B ist ein etwas komplizierter Prozess. Ich kann nicht glauben, es aus der Spitze von meinem Kopf, aber ich weiß, es ist gut definiert (und wahrscheinlich geht es um die Schaffung Mitgliedstaaten auf, die stellen die Produkte von akzeptierenden Zuständen in A und nicht-akzeptierenden Zuständen in B).

    • Für a-B Ein, die Sie verwenden möchten, Schnittmenge und Komplement statt, die leider nicht Häufig in regex-Bibliotheken, die, wenn Sie umsetzbar sind, für das 'echte' regexes (anstelle des Perl-Art). (Weder ist die Prüfung, ob ein regex akzeptiert nichts. Bibliotheken saugen, nicht wahr?)
    InformationsquelleAutor Edmund
  3. 2

    Dies hängt wirklich davon ab, was du damit meinst reguläre Ausdrücke. Wie die anderen Poster wies darauf hin, reduzieren beide Ausdrücke auf Ihren minimalen DFA sollte funktionieren, aber es funktioniert nur für die Reine reguläre Ausdrücke.

    Einige Konstrukte verwendet, die in der realen Welt regex-libs (Rückverweise im besonderen) geben Ihnen die Kraft, um auszudrücken, Sprachen, die nicht regulär, so ist die DFA-Algorithmus funktioniert nicht für Sie. Zum Beispiel regex : ([a-z]*) \1 entspricht eine doppelte vorkommen des gleichen Wortes durch ein Leerzeichen getrennt (a a und b b aber nicht b a noch a b). Dies kann nicht erkannt werden, die von einem endlichen Automaten überhaupt.

    InformationsquelleAutor Rafał Dowgird
  4. 1

    Diese beiden Perlmonks threads über diese Frage (insbesondere Lesen blokhead Antworten):

    InformationsquelleAutor codelogic
Schreibe einen Kommentar