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

11

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?

— Richard Jones
źródło

1

Tak, jest to rozstrzygalne w czasie liniowym drona.csa.iisc.ernet.in/~deepakd/atc-common/…

— abc

1

Witamy w informatyce! Czego próbowałeś? Gdzie utknąłeś? Nie chcemy wręczać ci rozwiązania; chcemy, abyście zrozumieli. Ponieważ jednak nie wiemy, na czym polega Twój problem, nie możemy zacząć pomagać. Zobacz tutaj wskazówki dotyczące zadawania pytań na temat problemów z ćwiczeniami. Jeśli nie jesteś pewien, jak poprawić swoje pytanie, dlaczego nie zapytać na czacie informatyki ?

— Raphael

22

Aby zdecydować, czy języki generowane przez dwa DFA przez to samo, konstruuj DFA dla różnicy symetrycznej i sprawdź, czy . $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. $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)$

— Yuval Filmus
źródło

3

Biorąc pod uwagę dwa DFA i , równość i i sprawdzenie, czy i generują ten sam język, są tymi samymi rzeczami. $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_1$ $D_2$

— fade2black
źródło

1

Wierzę, że łączysz „równoważność” DFA i ich równości.

— einpoklum

@einpoklum tak, używam terminu „równość” jako synonim „równoważności”, ponieważ OP używa terminu „Równość”.

— fade2black

2

Oba nie są takie same. Nawet po minimalizacji automaty nie są równe . Wiemy jednak, że są izomorficzne, co z pewnością jest rozstrzygalne (jeśli potencjalnie trudniejsze niż równość).

— Raphael