Skip to main content
Added explanation of the algorithm
Source Link

I don't think it's correct to look at the equivalence of DFA's as an isomorphism of their graph representation, as two DFA's accepting the same language may have different numbers of states(nodes), from graph point of view they will not be isomorphic but they happen to be equivalent as they accept the same language.

You could create a product automata accepting the language $L = L_{1} \oplus L_{2}$ using the given two DFA, here if $L$ is empty that means there exists no string that is present in $L_{1}$ and not present in $L_{2}$ and no string that is present in $L_{2}$ and not present in $L_{1}$, hence our languages will be equal.

Now we have a product DFA (directed graph) and we have to check if it's the language accepted by it is empty or not, this can be done by performing a DFS/BFS from the start state of our product DFA.

If no final state is reachable in our DFS/BFS from the start state ($L$ is empty) then the languages $L_{1}$ and $L_{2}$ are equal else if there is a final state reachable ($L$ is not empty) then the languages are not equal.

I don't think it's correct to look at the equivalence of DFA's as an isomorphism of their graph representation, as two DFA's accepting the same language may have different numbers of states(nodes), from graph point of view they will not be isomorphic but they happen to be equivalent as they accept the same language.

I don't think it's correct to look at the equivalence of DFA's as an isomorphism of their graph representation, as two DFA's accepting the same language may have different numbers of states(nodes), from graph point of view they will not be isomorphic but they happen to be equivalent as they accept the same language.

You could create a product automata accepting the language $L = L_{1} \oplus L_{2}$ using the given two DFA, here if $L$ is empty that means there exists no string that is present in $L_{1}$ and not present in $L_{2}$ and no string that is present in $L_{2}$ and not present in $L_{1}$, hence our languages will be equal.

Now we have a product DFA (directed graph) and we have to check if it's the language accepted by it is empty or not, this can be done by performing a DFS/BFS from the start state of our product DFA.

If no final state is reachable in our DFS/BFS from the start state ($L$ is empty) then the languages $L_{1}$ and $L_{2}$ are equal else if there is a final state reachable ($L$ is not empty) then the languages are not equal.

Source Link

I don't think it's correct to look at the equivalence of DFA's as an isomorphism of their graph representation, as two DFA's accepting the same language may have different numbers of states(nodes), from graph point of view they will not be isomorphic but they happen to be equivalent as they accept the same language.