2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\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$ – Umbert Apr 5 '16 at 2:31
  • $\begingroup$ Where did you find this definition? $\endgroup$ – J.-E. Pin Apr 5 '16 at 9:14

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.