Является ли равенство двух DFA решаемой проблемой?

Итак, учитывая два DFA, является ли проблема обнаружения, если они генерируют один и тот же язык, разрешимой проблемой?

Я уже знаю, что равенство двух КЛЛ не является разрешимым

а как насчет равенства двух ДФА? учитывая, что большинство проблем с DFAs разрешимы, это тоже разрешимо?

$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$

$A_\Delta$$(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$

$L(A_\Delta)$

Учитывая два DFA и D 2 , равенство D 1 и D 2 и проверка, генерируют ли D 1 и D 2 один и тот же язык, - это одно и то же.$D_1$$D_2$$D_1$$D_2$$D_1$$D_2$

Да, эта проблема разрешима. Вы можете минимизировать как и D 2 и сравнить их функции перехода. Учитывая DFA, алгоритм минимизации уменьшает количество состояний до минимального числа, и этот DFA является уникальным. Вот альтернативный подход.$D_1$$D_2$