Ist die Gleichheit zweier EDA ein entscheidendes Problem?

Ist das Problem, bei zwei DFAs herauszufinden, ob sie dieselbe Sprache erzeugen, ein entscheidbares Problem?

Ich weiß bereits, dass die Gleichheit von zwei CFL nicht entscheidbar ist

aber was ist mit der Gleichheit von zwei DFAs? Wenn man bedenkt, dass die meisten Probleme mit DFAs entscheidbar sind, ist dies auch entscheidbar?

Um zu entscheiden , ob die erzeugten Sprachen von zwei DFAs durch denselben, ein DFA - Konstrukt A Δ für die symmetrische Differenz L ( A 1 ) Δ L ( A 2 ) : = ( L ( A 1 ) ∖ L ( A 2 ) ) ∪ ( L ( A 2 ) ∖ L ( A 1 ) ) und prüfen Sie, ob$A_1,A_2$$A_\Delta$$L(A_1) \Delta L(A_2) := (L(A_1) \setminus L(A_2)) \cup (L(A_2) \setminus L(A_1))$ .$L(A_\Delta) = \emptyset$

Hier sind einige weitere Details. Sie können konstruieren mit dem Produktaufbau : eine Produktautomat konstruieren, und die Verwendung ( F 1 × ¯ F 2 ) ∪ ( ¯ F 1 × F 2 ) als die Menge der Zustände anzunehmen.$A_\Delta$$(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$

Um zu überprüfen, ob leer ist oder nicht, reicht es aus, zu überprüfen, ob ein akzeptierender Zustand vom Anfangszustand aus erreichbar ist, und dies kann unter Verwendung von BFS / DFS erfolgen.$L(A_\Delta)$

Bei zwei DFA und D 2 sind die Gleichheit von D 1 und D 2 und die Überprüfung, ob D 1 und D 2 dieselbe Sprache erzeugen, dasselbe.$D_1$$D_2$$D_1$$D_2$$D_1$$D_2$

$D_1$$D_2$