I have a DFA A, I minimize A and the minimized DFA obtained is M. My question is if in general A and M are isomorphic?

  • $\begingroup$ That would only be true if all DFA had the same size as the smallest equivalent one. What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Apr 16 '16 at 18:53
  • $\begingroup$ Please edit your question to show what you've tried and what specifically prevents you from figuring out the answer on your own. Have you tried working through some examples? If so, show us an example or two and what your thoughts are. It might help to define what you mean by "isomorphic", and to tell us whether you understand that definition. Do you mean, "accepts the same language"? Or, do you mean "isomorphic as graphs"? Do you mean "the same up to relabelling of states"? $\endgroup$
    – D.W.
    Apr 16 '16 at 20:19

No. If the result of minimizing was always isomorphic to the thing you started with, minimization would do nothing!

For a concrete example, consider any automaton with more than one state, which has every state accepting. This automaton accepts $\Sigma^*$ and is not isomorphic to the minimal automaton for that language, which has just one state.

  • $\begingroup$ Right. Your counterexample is in effect a demonstration. Thank you $\endgroup$
    – Umbert
    Apr 16 '16 at 18:38

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.