This is a question from a MCQ competitive exam: Let $L$ be the set of all binary strings whose last two symbols are the same. What are the number of states in the minimum state deterministic finite-state automaton accepting $L$?
The answer is 5 according to the solution key though no method is specified.
My attempt at solving is to use the Myhill-Nerode theorem i.e. by partitioning the language into equivalence classes. My understanding is that the number of classes is the number of states needed in the DFA.
I can immediately think of three equivalence classes:
- non-empty strings ending at $0$
- non-empty strings ending at $1$
- empty strings
I believe this covers all the possible classes. If so, then the number of states in the DFA should only be 3. Try as I might I could not construct this DFA. Clearly I'm missing something.