1
$\begingroup$

Consider 2 DFAs both determining a language $L$. Both DFAs have the same number of states $n$. Can I then conclude that these two DFAs are isomorphic?

I think the answer is yes, because if I'd make an $MN(L)$ relation with $n$ equivalence classes and map it to a $DFA$, there'd only be one result (at least I believe so). Thus both of the DFAs map to the same $MN(L)$ relation.

Is this reasoning correct?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let $M$ be a DFA for the language $L$ and let $M_1$ and $M_2$ be $M$ with two different collections of some number $m$ of unreachable states added. $M_1$ and $M_2$ both have the same number of states and both accept $L$, but they need not be isomorphic.

For a less trivial example, consider the following two DFAs:

Start state: 1
Accepting states: 2, 4
1 -a-> 2   1 -b-> 1
2 -a-> 3   2 -b-> 2
3 -a-> 4   3 -b-> 3
4 -a-> 1   4 -b-> 4

Start state: 1
Accepting states: 2, 4
1 -a-> 2   1 -b-> 3
2 -a-> 3   2 -b-> 4
3 -a-> 4   3 -b-> 1
4 -a-> 1   4 -b-> 2

These two 4-state DFAs are non-isomorphic, but both accept the same language, namely the language of all strings over the alphabet $\{a, b\}$ which have an odd number of $a$s.

Note that if two DFAs accepting the same language have the same number of nodes, and that number is minimal among DFAs accepting that language, then the two DFAs must be isomorphic. See DFA minimization.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That makes sense! So what about 2 DFAs with no unreachable states? $\endgroup$
    – Bram Vanbilsen
    Commented Jan 5, 2020 at 19:36
  • $\begingroup$ @Bram I have edited my answer with another example. $\endgroup$
    – Aaron Rotenberg
    Commented Jan 5, 2020 at 21:10

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.