Allgemeiner Beweis der Äquivalenz zweier FSMs in endlicher Zeit?

Question

Gibt es einen allgemeinen Beweis für die Äquivalenz zweier (deterministischer) endlicher Automaten, die immer endliche Zeit benötigen? Können Sie also bei zwei FSMs beweisen, dass sie bei gleichen Inputs immer die gleichen Outputs produzieren, ohne die FSMs tatsächlich ausführen zu müssen (die nicht terminierend sein könnten?). Wenn ein solcher Beweis existiert, wie hoch ist die zeitliche Komplexität?

Answer 1

Es gibt einen Beweis, obwohl ich es nicht weiß. Suchen Sie nach Sipsers Lehrbuch zu diesem Thema, von dem ich es kenne.

Verschlingen meines Gedächtnisses: Im Grunde gibt es ein einzigartiges minimales DFA für ein gegebenes DFA, und es gibt einen Minimierungsalgorithmus, der immer endet. Minimiere sowohl A als auch B und überprüfe, ob sie den gleichen minimalen DFA haben. Ich kenne die Komplexität der Minimierung nicht, obwohl sie nicht zu schlecht ist (ich denke an ihr Polynom). Graph Isomorphie ist ziemlich schwer zu berechnen, aber da es einen speziellen Startknoten gibt, ist es hoffentlich etwas einfacher. Sie müssen nicht einmal Graph Isomorphie verlangen, um ehrlich zu sein.

Aber nein, Sie müssen die DFAs nicht wirklich ausführen, sondern nur deren Struktur analysieren.

Answer 2

Angenommen, Sie haben zwei FSMs mit O (n). Dann können Sie eine FSM der Größe O (n) erstellen, die nur die symmetrische Differenz ihrer akzeptierten Sprachen erkennt. (Machen Sie eine FSM, die Zustände hat, die einem Zustandspaar entsprechen, eines aus jeder FSM. Aktualisieren Sie dann bei jedem Schritt jeden Teil des Paars gleichzeitig. Ein Zustand in der neuen FSM ist ein Akzept-Zustand, wenn genau einer der Paare war ein Akzeptieren-Zustand.) Minimieren Sie jetzt diese FSM und sehen Sie, ob es das gleiche wie die triviale Ein-Zustands-FSM ist, die alles ablehnt. eine FSM mit m Staaten Minimierung braucht Zeit O (m log m), also insgesamt Sie alles, was in der Zeit O tun können (n log n).

@Agor korrekt angibt, dass Sipser eine gute Referenz für diese Art von Dingen ist. Der Schlüsselpunkt meiner Antwort ist, dass Sie dies in polynomieller Zeit tun können, sogar mit einem kleinen Exponenten.