Czy równość dwóch DFA jest rozstrzygającym problemem?

Czy biorąc pod uwagę dwa DFA, problem ze znalezieniem, czy generują ten sam język, stanowi problem rozstrzygalny?

Wiem już, że równość dwóch CFL nie jest rozstrzygalna

ale co z równością dwóch DFA? biorąc pod uwagę, że większość problemów związanych z DFA jest rozstrzygalna, czy to również jest rozstrzygalne?

Aby zdecydować, czy języki generowane przez dwa DFA przez to samo, konstruuj DFA dla różnicy symetrycznej i sprawdź, czy .A Δ L ( A 1 ) Δ L ( A 2 ) : = ( L ( A 1 ) ∖ L ( A 2 ) $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$

Oto kilka szczegółów. Możesz zbudować używając konstrukcji produktu : automat produktu i użyj jako zestaw stanów akceptujących. ( F 1 × ¯ F 2 ) ∪ ( ¯ F 1 × F 2$A_\Delta$$(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$

Aby sprawdzić, czy jest pusty, czy nie, wystarczy sprawdzić, czy jakiś stan akceptacji jest osiągalny ze stanu początkowego, i można to zrobić za pomocą BFS / DFS.$L(A_\Delta)$

Biorąc pod uwagę dwa DFA i , równość i i sprawdzenie, czy i generują ten sam język, są tymi samymi rzeczami.D 2 D 1 D 2 D 1 D $D_1$$D_2$$D_1$$D_2$$D_1$$D_2$

Tak, ten problem jest rozstrzygalny. Możesz zminimalizować zarówno jak i i porównać ich funkcje przejścia. Biorąc pod uwagę DFA, algorytm minimalizacji zmniejsza liczbę stanów do minimalnej liczby, a ten DFA jest unikalny. Oto alternatywne podejście.D $D_1$$D_2$