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!
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Please post your 6-state solution for scrutiny. $\endgroup$– Devendra BhaveCommented Apr 19, 2017 at 2:45
-
$\begingroup$ Does it have to be a DFA? Or is an NFA okay? $\endgroup$– Luke MathiesonCommented Apr 19, 2017 at 3:01
-
2$\begingroup$ @Devendra Please don't. We're not in the business of grading people's work. $\endgroup$– David RicherbyCommented Apr 19, 2017 at 9:04
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
[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$.
-
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$– zfzaCommented Apr 19, 2017 at 16:15
$\begingroup$
$\endgroup$
[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)