$\begingroup$

I have this diagram of a DFA:

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$ 7

1 Answer

$\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

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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