given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent states. The minimum DFA will be unique unless the names of states. Now my question is what is the difference between minimal and canonical DFA? They are the same thing?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Yes. The canonical DFA for a regular language $L$ is the automaton that is based on the equivalence classes of the relation defined by $L$, i.e., they cannot be "distinguished" in $L$ by extending them with the same suffix.
It is part of the Myhill-Nerode results that that yields a minimal DFA for $L$.
answered Apr 5, 2016 at 2:20
-
$\begingroup$ I know that theorem (at least the results). But I have this definition for canonical DFA: Let A be a minimal DFA. If each DFA A' with the same number of states is isomorphic to A, A is called the canonical DFA. And I do not understand the necessity of this definition $\endgroup$– NickApr 5, 2016 at 2:31
-