Question 63

The language $L = (0 + 1)^* 10$ consists of all binary strings ending in $10$.

Define the state states based on the longest matching suffix of $10$ seen so far:

• State $A$ (start): Last symbol is not 1 (matched suffix $\epsilon$).
• State $B$: Last symbol seen is 1 (matched suffix 1).
• State $C$ (accepting): Last two symbols seen are 10 (matched suffix 10).

Transitions:

• From $A$: on $0 \to A$, on $1 \to B$.
• From $B$: on $1 \to B$, on $0 \to C$.
• From $C$: on $0 \to A$, on $1 \to B$.

All 3 states are reachable and pairwise distinguishable by the Myhill-Nerode theorem:

• $\epsilon$ separates $C$ (accepting) from $A$ and $B$.
• Input string 0 sends $B$ to $C$ (accept) but keeps $A$ in $A$ (reject).

Hence, the minimal DFA requires exactly 3 states.