[Math] Construct a deterministic finite state automaton

automatacomputer sciencediscrete mathematics

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10.

enter image description here

This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing anything?

EDIT: Think this is it.

A few changes.

Best Answer

Your DFA recognizes the strings that contain $10$ somewhere as a substring. You want to recognize only those that end in $10$ (though they may of course have other $10$ substrings internally). You need to change the transitions out of $s_2$. If you’re in $s_2$ and get any more input, you’re essentially starting over as if you were in $s_0$ getting the very first input. Thus, an input of $0$ should just take you back to $s_0$. Where should an input of $1$ take you?

Related Question