Timeline for Automata: Are there algorithms to judge whether two automata are isomorphic?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 31, 2022 at 1:33 | comment | added | XYJ | Thank you for your comment. I'll try to search for it more on the Internet. | |
| Dec 30, 2022 at 23:50 | comment | added | reinierpost | Yes, exactly. Look up full explanations with Google. I could formalize what I wrote above, but it's been done by professionals elsewhere. | |
| Dec 30, 2022 at 14:53 | comment | added | XYJ | 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. | |
| Dec 30, 2022 at 13:41 | comment | added | reinierpost | 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. | |
| Dec 30, 2022 at 13:33 | comment | added | reinierpost | 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. | |
| Dec 30, 2022 at 3:39 | comment | added | XYJ | 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. | |
| Dec 29, 2022 at 23:51 | history | edited | reinierpost | CC BY-SA 4.0 | deleted 1 character in body |
| Dec 29, 2022 at 19:36 | history | answered | reinierpost | CC BY-SA 4.0 |