# Are every 2 DFAs with $n$ states for a language $L$ isomorphic to each other?

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?

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.

• That makes sense! So what about 2 DFAs with no unreachable states? Jan 5, 2020 at 19:36
• @Bram I have edited my answer with another example. Jan 5, 2020 at 21:10