I'm having trouble coming up with a 5-state DFA that, on all inputs of length 8, recognizes the string 00001111 and no other string (of length 8). The DFA must have an exiting transition for every symbol in the alphabet (namely {0, 1}). The behavior on input of other lengths does not matter. A 6-state solution is pretty simple, but reducing down to 5 states requires more sophistication.
Any help would be appreciated!

  • 2
    $\begingroup$ Please post your 6-state solution for scrutiny. $\endgroup$ – Devendra Bhave Apr 19 '17 at 2:45
  • $\begingroup$ Does it have to be a DFA? Or is an NFA okay? $\endgroup$ – Luke Mathieson Apr 19 '17 at 3:01
  • 2
    $\begingroup$ @Devendra Please don't. We're not in the business of grading people's work. $\endgroup$ – David Richerby Apr 19 '17 at 9:04

[If I understand the question correctly, this only relates to strings of length 8, i.e. for an automata $A$ we only look at $L(A) \cap \Sigma^8$]

There is a slight variance in interpretation of what a DFA is that plays a role here.

You can construct a DFA with 5 states that accepts $00001111$, but it is not complete, meaning not every state has an exiting transition for every symbol of the alphabet. This quesiton addresses this point in more details.

What this difference in notation allows you to do is skip the sink-node: DFA without sink state

If the input string is of length 8, this automaton accepts only $00001111$.

  • 2
    $\begingroup$ The definition of a DFA I use here is that every state must have an exiting transition for every symbol of the alphabet, so the above DFA would not be valid. I will edit the original question. $\endgroup$ – zfza Apr 19 '17 at 16:15

[Note: I'll add this as a separate answer to keep both answers for posterity. This answer satisfies the conditions added later in the question.]

This is a 5-state DFA which, when provided only with inputs of length 8, only accepts the string 00001111:


(I should also note that I didn't come up with this solution myself. I wrote a quick tool to brute-force through 5-state DFAs to find this one)


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.