I am having a little trouble understanding this question.
For a DFA M = (Q, Σ, δ, q0, F), we say that a state q ∈ Q is reachable if there exists some string w ∈ Σ∗ such that q = δ∗(q0, w).
Give an algorithm that, given as input a DFA expressed as a five-tuple M = (Q, Σ, δ, q0, F), returns the set of all of M’s reachable states.
Can anyone help me understand and answer this question?
Someone hands you a DFA $M=\langle Q,\Sigma,\delta,q_0,F\rangle$, i.e., a set of states, an input alphabet, a transition function, an initial state, and a set of acceptor states. You’re to come up with an algorithm — a systematic procedure — that takes this information as input and produces as output a list of the reachable states of $M$.
A first easy observation is that you can ignore $F$ altogether: you don’t care which states are accepting, just which ones can actually be reached from $q_0$ with some input. You will need to use the other four items, however. A second easy observation is that $q_0$ is reachable, since $\delta^*(q_0,\epsilon)=q_0$, where $\epsilon$ is the empty word.
If $\Sigma=\{\sigma_1,\ldots,\sigma_n\}$, the natural thing to do is to start by running $M$ with all $n$ one-symbol inputs; that will tell you which states are reachable in one transition. Then you could systematically test inputs of length $2$:
$$\sigma_1\sigma_1,\sigma_1\sigma_2,\ldots,\sigma_1\sigma_n,\sigma_2\sigma_1,\sigma_2\sigma_2,\ldots,\sigma_2\sigma_n,\ldots,\sigma_n\sigma_n\;.$$
And you could go on to longer and longer inputs. The only real question is how to know when to stop: at what point can you be sure that you’ve found all of the reachable states?
HINT: If there are $m$ states, how long a word must you input in order to guarantee that the DFA will visit some state twice while reading the word?