2
$\begingroup$

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!

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

2 Answers 2

5
$\begingroup$

[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$.

$\endgroup$
1
  • 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, 2017 at 16:15
4
$\begingroup$

[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:

DFA

(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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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