Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

share|cite|improve this answer
    
And that's even infinitely many up to isomorphism. – G. Bach Feb 4 at 8:39
    
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 :) – Shaull Feb 4 at 9:59
    
Infinitely many different DFAs even for finite languages? – Bergi Feb 4 at 15:17
1  
@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. – Shaull Feb 4 at 15:21
    
@Shaull: You mean with ε-transitions or unreachable states? OK, I didn't consider those. – Bergi Feb 4 at 15:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.