0
$\begingroup$

I have this diagram of a DFA:

webber_ch2_6c.png

I have written that DFA as 5-tuple $(Q, \Sigma, \delta, q_0, F )$ where:

  • $Q$ is the set of all states: $Q = \left \{ q_0, q_1, q_2\right \}$;
  • $\Sigma$ is the alphabet: $\Sigma = \left \{ 0, 1 \right \}$;
  • $\delta$ is the transition function;
  • $q_0$ is the initial state;
  • $F$ is the set of final states: $F = \left\{ q_0, q_2\right \}$.

and I have written the transition function $\delta$:

$\begin{array}{rcl}\delta(q_0, 0) & = & q_1 \\ \delta(q_0, 1) & = & q_2 \\ \delta(q_1, 0) & = & q_1 \\ \delta(q_1, 1) & = & q_1 \\ \delta(q_2, 0) & = & q_2 \\ \delta(q_2, 1) & = & q_2 \end{array}$

therefore I understand that:
- if the DFA is in state $q_0$ and reads symbol $0$, $0$ will be rejected;
- if the DFA is in state $q_0$ and reads symbol $1$, $1$ will be accepted.

but what I don't understand is:

what's the meaning of that accepting state in $q_0$?
Does it mean that, if the input is an empty string $\epsilon$, then, that empty string will be accepted and the DFA stops?

Please, can you explain me better? Many thanks!

$\endgroup$
  • 1
    $\begingroup$ It always starts at $q_0$. If all the input is read in and it's in the state $q_0$, then it'll accept the input. :) I.e. empty input is accepted. $\endgroup$ – Andrew Mar 25 '17 at 20:07
  • $\begingroup$ @Andrew Thanks! So, you have also explained a general case, in the first part of your answer. In this example, "all input" you said, it is the unique input formed only by empty string $\epsilon$. - Instead, considering this DFA: s26.postimg.org/9ad5hg0rd/automa_start_finish.png, here, it is valid both the empty string alone, and a string as "0110". $\endgroup$ – JB-Franco Mar 25 '17 at 21:41
  • 1
    $\begingroup$ What you linked will accept a string iff it has an even number of $1$s in it. That includes both the empty string and "0110". $\endgroup$ – Andrew Mar 25 '17 at 21:44
  • $\begingroup$ it will accept therefore string as, $\epsilon, 011, 0110$ etc... $\endgroup$ – JB-Franco Mar 25 '17 at 21:46
  • 1
    $\begingroup$ @Andrew Why don't you have put the first sentence you wrote as answer? With that, you have answered me exactly to what I want! $\endgroup$ – JB-Franco Mar 25 '17 at 21:53
2
$\begingroup$

The machine always starts at $q_0$. If all of the input string is read, and it's in the state $q_0$, then it'll accept the input. That is, the empty input in this case will also be accepted!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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