16
$\begingroup$

For Example when we consider a DFA that allows the strings having neither sub strings 00 or 11 I can produce the following two DFAs:

enter image description here

$\endgroup$
37
$\begingroup$

First of all, your left DFA is incorrect - it accepts e.g. 011.

Secondly, DFAs can be canonically minimized, so in that sense, you can always find one canonical DFA for a certain language.

But in general, there are infinitely many different DFAs for every language, so you could get different correct answers.

$\endgroup$
  • $\begingroup$ And that's even infinitely many up to isomorphism. $\endgroup$ – G. Bach Feb 4 '16 at 8:39
  • $\begingroup$ To be even more specific: it's infinite up to isomorphism when the states are a subset of a fixed set, e.g. $\mathbb{N}$. If we don't fix that, the collection of automata is not even a set... Somehow I don't think this was the intention of the OP :) $\endgroup$ – Shaull Feb 4 '16 at 9:59
  • $\begingroup$ Infinitely many different DFAs even for finite languages? $\endgroup$ – Bergi Feb 4 '16 at 15:17
  • 1
    $\begingroup$ @Bergi : Certainly - you can add as many redundant states as you like. This may sound "silly", and it is indeed senseless when you construct an automaton yourself. However, many times automata are constructed by translating from some other formalism (e.g. determinization of NFAs), in which case you are very likely to get redundant states. $\endgroup$ – Shaull Feb 4 '16 at 15:21
  • $\begingroup$ @Shaull: You mean with ε-transitions or unreachable states? OK, I didn't consider those. $\endgroup$ – Bergi Feb 4 '16 at 15:31

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.