# Smallest possible DFA for a language over {0,1}* with third to last symbol 1 should have 4 states not 8. Where am I going wrong in my DFA?

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

Now, I came up with a much better DFA with only 4 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)

• 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. – D.W. Mar 19 '18 at 19:46

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}$$