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?

$\endgroup$
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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