1
$\begingroup$

When I want to judge whether two regular forms represent the same language, I have learned the next method:

  1. create the (non-deterministic) finite-state automata which accepts the language the given regular form represents for two regular forms respectively.

  2. convert the two NFA into DFAs.

  3. Judge whether the two DFAs are isomorphic.

However, I don't really know how to do 3.

Are there any algorithms to do 3? In more general, how to judge whether two given graphs is isomorphism. (If both graph is non-labeled, I think it is very difficult and I'm not sure how to do it.)

Thank you.

Notation There is already a question regarding algorithms to judege the equivalence of two automata and the method is different from above one. Although that way is much smarter, I am wondering whether it is possible to judge the equivalence of two automata in the direction above.

Thus, I want to just learn about the algorithms to judge whether two DFAs (or graphs) are isomorphic.
What I want to do is to distinguish automata by whether their shape, that is, if two given automata is not isomorphic, then they should be regarded as "different", even if they accept the same language.

Improve this question
$\endgroup$
4
  • $\begingroup$ stackoverflow.com/questions/6905043/… $\endgroup$
    – Rinkesh P
    Commented Dec 25, 2022 at 3:56
  • $\begingroup$ @RinkeshP Thank you for your comment. Actually, I am not sure the difference between many projects of the Stack Exchange, e.g. "Stack Overflow" and "Computer Scienece" (this site). I recognize Stack Overflow is more related to programming and "Computer Science" is more related to the theoritical part. Is this right? Thank you. $\endgroup$
    – XYJ
    Commented Dec 25, 2022 at 9:10
  • $\begingroup$ Yes, that's right, that post could have been posted on CS.SE instead of SO. $\endgroup$
    – Nathaniel
    Commented Dec 26, 2022 at 0:08
  • $\begingroup$ Thank you for your comment. Sometimes, it is surely helpful to looking at SO and various sites, even though the question I want to ask is regarding theoritical part of computer science. $\endgroup$
    – XYJ
    Commented Dec 26, 2022 at 9:14

2 Answers 2

Reset to default
2
$\begingroup$

DFAs can be minimized. The minimal DFA for a regular language is unique up to isomorphism. So you can compare them by walking both transition graphs in parallel, in the same order, e.g. depth-first. As soon as you find a mismatch, the DFAs aren't isomorphic; once you've visited all states and transitions without any mismatch, they are isomorphic.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your answer. I'm wondering how to do the DFS because I think there is no difference in each children vertex of a vertex. For example, if there's three children nodes in the starting node in both automata, how to know which children node correspond to which in the two automata? Thank you. $\endgroup$
    – XYJ
    Commented Dec 30, 2022 at 3:39
  • $\begingroup$ Those three children are connected with different symbols (because it's a DFA). While walking both graphs you need to build a 1-to-1 mapping of the states. It must turn out to be a bijection. That is to say, as soon as you find a child missing at one end (i.e. a symbol for which a transition exists on one side and not the other), or a child that is equal to a state visited earlier at one end while the corresponding child at the other end is not equal to the corresponding state at that end, you know you can't complete the bijection, and (because they're DFAs) that implies that none exists. $\endgroup$
    – reinierpost
    Commented Dec 30, 2022 at 13:33
  • $\begingroup$ Incidentally: the same algorithm can be run on two arbitrary NFAs, except that instead of constructing a bijection between the states of the two automata, you construct a bijection between sets of states of the two automata. It's a little trickier because of $\epsilon$-transitions. $\endgroup$
    – reinierpost
    Commented Dec 30, 2022 at 13:41
  • $\begingroup$ Thank you for your comments. I think that in the beginning, it is unknown which child corresponds to which child in another DFA. Then, I put a random input string into both DFA and define regard states after reading one alphabet in both DFAs as corresponding. We define the correspondence similarly for other states. Then, when you insert another input string and find that the correspondence does not stand in that input string, we judge that the two DFAs are not isomorphic. Is my understanding right? I would be grateful if you could give me a comment. $\endgroup$
    – XYJ
    Commented Dec 30, 2022 at 14:53
  • $\begingroup$ Yes, exactly. Look up full explanations with Google. I could formalize what I wrote above, but it's been done by professionals elsewhere. $\endgroup$
    – reinierpost
    Commented Dec 30, 2022 at 23:50
1
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Thank you for your answer. I found my question is not clear, so I edited it. Although I understand there are many other algorithms to judge the equivalence of two automata, I would like to know the detail algorithm based on the direction shown in my question, especially about how to judge the isomorphism of two graphs (or automata). $\endgroup$
    – XYJ
    Commented Dec 28, 2022 at 10:42
  • $\begingroup$ @XYJ I have added details on how you can proceed after the 3rd step mentioned in the question $\endgroup$
    – Arun Madhav
    Commented Dec 28, 2022 at 12:27
  • $\begingroup$ Thank you for your answer. Creating a new automaton that accepts the union of two automata is very useful way. The similar method appears in another algorithm of judging equivalence of two automata. $\endgroup$
    – XYJ
    Commented Dec 28, 2022 at 13:38
  • $\begingroup$ By the way, does $L_1\oplus L_2$ means $L_1\cup L_2$? $\endgroup$
    – XYJ
    Commented Dec 28, 2022 at 13:39
  • 2
    $\begingroup$ Thank you for your answer. I think the method is similar to ones in another algorithm of checking the equivalence of two automata in this questions on Stack Overflow. I realized this approach is really useful. $\endgroup$
    – XYJ
    Commented Dec 28, 2022 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.