# 5-state DFA that recognizes only the string 00001111

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!

• Please post your 6-state solution for scrutiny. – Devendra Bhave Apr 19 '17 at 2:45
• Does it have to be a DFA? Or is an NFA okay? – Luke Mathieson Apr 19 '17 at 3:01
• @Devendra Please don't. We're not in the business of grading people's work. – 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:

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

• 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. – zfza Apr 19 '17 at 16:15