1
$\begingroup$

So I was reading Micheal Sipser's Introduction to TOC and when I stumbled upon this aforementioned question , he'd the following dfa :

The dfa in the book

Now, I came up with a much better DFA with only 4 states :

My DFA with four states

I read in another thread that the minimum number of states for a DFA for this language is 8. But , I came up with 4.

Where am I going wrong ? (I tried testing this DFA with a plethora of input strings , seems ok to me)

$\endgroup$
  • $\begingroup$ For future reference, it would be better to give a link to the place where you read that fact (the minimum number of states is 8). Turns out not to matter this time, but it's best to give as much information as possible in the question. $\endgroup$ – D.W. Mar 19 '18 at 19:46
1
$\begingroup$

Try inputting 1100 to your DFA. You get to $q_1$, a non-accepting state.

We can show that 8 states are needed using the Myhill–Nerode theorem. The following table gives words separating any two of $000,001,010,011,100,101,110,111$: $$ \begin{array}{c|cccccccc} & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\\hline 000 & & 00 & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\ 001 & 00 & & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\ 010 & 0 & 0 & & 00 & \epsilon & \epsilon & \epsilon & \epsilon \\ 011 & 0 & 0 & 00 & & \epsilon & \epsilon & \epsilon & \epsilon \\ 100 & \epsilon & \epsilon & \epsilon & \epsilon & & 00 & 0 & 0 \\ 101 & \epsilon & \epsilon & \epsilon & \epsilon & 00 & & 0 & 0 \\ 110 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & & 00 \\ 111 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & 00 & \end{array} $$

| cite | improve this answer | |
$\endgroup$

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.