2
$\begingroup$

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

$\endgroup$
2
  • 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, 2014 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, 2014 at 12:37

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .