Minimal DFA for $1\Sigma^*0$

What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?

The following answer assumes that each state in a DFA must contain an outgoing edge for each symbol. Otherwise, you might need one state fewer.

Let us say that two words $x,y$ are equivalent modulo $L$ if for any word $z$, either both $xz$ and $yz$ are in $L$, or both of them are not in $L$.

If two words $x,y$ are not equivalent modulo $L$, and $A$ is any DFA accepting $L$, then the state of $A$ after reading $x$ must be different from the state of $B$ after reading $y$ (why?).

As a consequence, if $x_1,\ldots,x_n$ is a collection of words, any two of which are not equivalent modulo $L$, then any DFA for $L$ must contain at least $n$ states.

(Furthermore, it is known that if the minimal DFA for $L$ contains $n$ states, then we can find $n$ such words: for each state, we take some word leading to it; but we don't need this direction here.)

In your case, the following words are pairwise inequivalent: $\epsilon, 0, 1, 10$. To show this, we need to consider all six pairs:

• $\epsilon,0$ are inequivalent since $10 \in L$ but $010 \notin L$.

• $\epsilon,1$ are inequivalent since $0 \notin L$ but $10 \in L$.

• $\epsilon,10$ are inequivalent since $\epsilon \notin L$ but $10 \in L$.

• $0,1$ are inequivalent since $00 \notin L$ but $10 \in L$.

• $0,10$ are inequivalent since $0 \notin L$ but $10 \in L$.

• $1,10$ are inequivalent since $1 \notin L$ but $10 \in L$.

This shows that every DFA for $L$ contains at least $4$ states. Conversely, there is a DFA for $L$ containing $4$ states, which I will let you figure out.

StackExchange Computer Science Q#134561, answer score: 4