Versuch, einen Algorithmus zu finden, der 2 reguläre Ausdrücke akzeptiert und sagt, ob sie gleichwertig sind

Question

Ich versuche herauszufinden, was der Algorithmus wäre, indem ich zwei Sprachen L1 und L2 gebe, um festzustellen, ob sie gleichwertig sind (L1 = L2) .

Es ist überraschend schwierig, mit einem zu kommen, wie ich gefunden habe, obwohl ich ziemlich sicher bin, es zuerst zu einem DFA umgewandelt werden muss, und dann jeden von ihnen zu reduzieren, auf eine minimale DFA ..

Auch Ich weiß, wenn L1 - L2 und L2 - L1 leer sind, dann L1 = L2.

Wer gut mit Theorie hier?

Answer 1

Sie können eine Beschreibung eines einigermaßen effizienten Algorithmus zum Testen von z. Gleichheit hier:

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf

Dig durch Referenzen des Artikels zu anderen Lösungen zu finden, die weniger effizient sein können, aber einfacher zu implementieren.

Answer 2

Hier ist eine konzeptionell einfache Antwort (vorausgesetzt L1 und L2 sind regulär).

1) Die DFAs D1 und D2 für L1 bzw. L2 suchen.

2) Konstruieren Sie D'1 und D'2 aus D1 und D2, indem Sie akzeptierende/nichtakzeptierende Zustände vertauschen (beachten Sie, dass D'1 genau ~ L1 akzeptiert und D'2 ~ L2 akzeptiert, wobei ~ "Komplement" bedeutet)

)

3) Verwenden Sie die Standard-Produktkonstruktion dreimal ein DFA zu erzeugen, die sich schneiden ~ L2) union (L2 schneiden ~ L1)

4) Überprüfen Sie, ob der DFA von Teil 3 übernimmt genau (L1 akzeptiert Alle Zeichenketten, indem jeder akzeptierende Zustand auf Erreichbarkeit vom Anfangszustand geprüft wird.

5) Wenn das DFA aus Teil 3 irgendwelche Zeichenfolgen akzeptiert, dann L1 <> L2. Ansonsten, L1 = L2

Es gibt eine große Anzahl von Heuristiken, die Sie verwenden könnten, um dies zu beschleunigen, aber konzeptionell ist dies wahrscheinlich der einfachste Algorithmus. Eine gute Referenz für die Produktkonstruktion in Teil 3 ist "Automata and Computability" von Dexter Kozen.