3
$\begingroup$

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?

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

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

enter image description here

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.