A igualdade de dois DFAs é um problema decidível?

Então, considerando dois DFAs, o problema de descobrir se eles geram o mesmo idioma é um problema Decidable?

Eu já sei que a Igualdade de duas CFL não é Decidable

mas e a igualdade de dois DFAs? considerando que a maioria dos problemas com os DFAs é decidível, isso também é decidível?

Para decidir se os idiomas gerados por dois DFAs pelo mesmo, construa um DFA para a diferença simétrica e verifique se .$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$

Aqui estão mais alguns detalhes. Você pode construir usando a construção do produto : construa um autômato de produto e use como o conjunto de estados de aceitação. ( F 1 × ¯ F 2 ) ∪ ( ¯ F 1 × F 2$A_\Delta$$(F_1 \times \overline{F_2}) \cup (\overline{F_1} \times F_2)$

Para verificar se está vazio ou não, basta verificar se algum estado de aceitação é acessível a partir do estado inicial, e isso pode ser feito usando o BFS / DFS.$L(A_\Delta)$

Dado dois DFA e , igualdade de e e verificar se e geram o mesmo idioma são as mesmas coisas.D 2 D 1 D 2 D 1 D $D_1$$D_2$$D_1$$D_2$$D_1$$D_2$

Sim, este problema é decidível. Você pode minimizar tanto e e comparar as suas funções de transição. Dado um DFA, o algoritmo de minimização reduz o número de estados para um número mínimo e esse DFA é único. Aqui está uma abordagem alternativa.D $D_1$$D_2$