# Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction:

Let $M=(Q,\Sigma,s,F,\triangle)$ be an NFA. Then there must exist a DFA $M'=(Q',\Sigma',s,F,\delta)$....

I understand that $Q'=2^{|Q|}$ because $Q'$ really is the power set of $Q$. And I know that not every state in $Q'$ is reachable. However, I am having a hard time to visualize which states are reachable.

So my question is, say, I have a nondetermistic finite automata NFA which is already deterministic. Now I still apply the same construction above to get the powerset. In this case, which states are reachable in the powerset $2^Q$?

• A state $S \subseteq Q$ in $M'$ is reachable if and only if there is an $\omega \in \Sigma^*$ such that $S$ is exactly the set of states of $M$ that can be reached by the word $\omega$ in $M$. Feb 21 '14 at 12:37
If by "NFA which is already deterministic" you mean an NFA that from each state and for each letter input it has only one choice to move, then the reachable states within the $2^Q$ states of the equivalent DFA are exactly the singletons.