# 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?

• According to me, the answer is 2. But I am not sure, have some doubt, so I am looking for your kind help. Jan 19, 2021 at 15:04
• Can you come up with a DFA having only two states? Jan 19, 2021 at 15:06

Let $$\mathcal{A} = \langle \Sigma, Q, q_0, \delta, F\rangle$$ be a DFA for $$L$$. Then, note that the $$|Q|\geq 4$$. Indeed, the states $$q_0, \delta(q_0, 0), \delta(q_0, 1)$$ have to be distinct, and clearly all of them are rejecting (can you tell why they're rejecting?) and thus as there are words in $$L$$, we know that there has to be at least one additional accepting state. To see why the later states are distinct, note that we have:

• from $$q_0$$ you can get to an accepting state, and from $$\delta(q_0, 0)$$ you cannot get to an accepting state. Hence, $$q_0$$ and $$\delta(q_0, 0)$$ are distinct.
• from $$\delta(q_0, 1)$$ you can get to an accepting state, and from $$\delta(q_0, 0)$$ you cannot get to an accepting state. Hence, $$\delta(q_0, 1)$$ and $$\delta(q_0, 0)$$ are distinct.
• from $$\delta(q_0, 0)$$ you cannot get to an accepting state, and from $$\delta(\delta(q_0, 1), 0)$$ you can get to an accepting state. Hence, $$q_0$$ and $$\delta(q_0, 1)$$ are distinct.

Now you can actually, build a DFA for L consisting of exactly 4 states. You can start from what we already know: the above three states are rejecting, and the 4'th additional state have to be accepting. So you only need to add the transitions between the 4 states properly.

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.

The minimal DFA is attached. Here, q0 is the initial state and q2 is the final state.