Allgemeiner Nachweis der Gleichwertigkeit von zwei FSMs in endlicher Zeit?

Question

Ist ein allgemeiner Beweis für die Äquivalenz von zwei (deterministischen) endlichen Automaten existiert, die immer endliche Zeit in Anspruch nehmen? Das heißt, zwei FSMs gegeben, können Sie beweisen, dass die gleichen Eingänge gegeben werden sie immer die gleichen Ausgaben erzeugen, ohne tatsächlich zu benötigen die FSMs auszuführen (was nicht abbreche sein könnte?). Wenn ein solcher Beweis nicht vorhanden ist, was ist die Zeitkomplexität?

Answer 1

Es ist ein Beweis, obwohl ich es nicht weiß. Sipser Lehrbuch zu diesem Thema suchen, das ist, wo ich weiß es aus.

scrounging mein Gedächtnis: im Grunde gibt es eine einzigartige minimale DFA für eine bestimmte DFA ist, und es gibt einen Minimierungsalgorithmus, der immer beendet. Minimieren sowohl A als auch B, und sehen, ob sie die gleiche minimale DFA haben. Ich weiß nicht, die Komplexität der Minimierung, obwohl seine nicht allzu schlecht (ich sein Polynom denken). Graphisomorphie ist ziemlich schwer zu berechnen, sondern weil es eine spezielle Ausgangsknoten ist, kann es hoffentlich etwas einfacher sein. Sie können nicht einmal Graphisomorphie erfordern, um ehrlich zu sein.

Aber nein, Sie müssen nicht immer, um tatsächlich die DFAs laufen, nur um ihre Struktur analysieren.

Answer 2

Angenommen, Sie haben zwei FSMs mit O ( n ) Staaten. Dann können Sie eine FSM der Größe O machen ( n ² ), die nur die symmetrische Differenz ihrer akzeptieren Sprachen erkennen. (Machen eine FSM, die Zustände, die zu einem Paar von Zuständen entsprechen hat, eine von jedem FSM. Dann auf jeden Schritt Aktualisieren jeden Teils des Paares gleichzeitig. Ein Zustand, in dem neuen FSM ist ein Zustand eines des Paares iff genau annehmen wurde eine Annahme Zustand.) Nun diese FSM minimieren und sehen, ob es das gleiche wie das trivial-Zustand FSM, der alles ablehnt ist. Minimieren einer FSM mit m Staaten braucht Zeit O ( m log m ), also insgesamt kann man alles in der Zeit O tun ( n ² log n ).

@Agor heißt es richtig, dass Sipser eine gute Referenz für diese Art von Dingen ist. Der entscheidende Punkt meiner Antwort ist, dass Sie dies in polynomialer Zeit tun können, sogar mit einem kleinen Exponenten.