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

Thanks in advance for your help!!!

  • 1
    $\begingroup$ What do you mean by a "NFA which is already deterministic?" Are you asking about the "easy" direction of the proof (that every DFA can be made into an equivalent NFA)? $\endgroup$ – D Wiggles Feb 19 '14 at 23:07
  • $\begingroup$ 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$. $\endgroup$ – Magdiragdag 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.


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.