How does the NFA decide in a state where there are multiple equally valid "next states"?
Such as here:
How does it decide on which state it takes to with 1?
$\begingroup$
$\endgroup$
10
-
$\begingroup$ Or perhaps this implies to always convert to the equivalent DFA? $\endgroup$– mavaviljDec 27, 2015 at 0:03
-
2$\begingroup$ It doesn't decide. It tries all legal trajectories, and accepts if at least one of them ends at an accepting state. $\endgroup$– Yuval FilmusDec 27, 2015 at 0:07
-
1$\begingroup$ Then nothing special happens. It still tries all legal trajectories. $\endgroup$– Yuval FilmusDec 27, 2015 at 0:10
-
1$\begingroup$ @mavavilj Then it's probably deterministic, or has explicit tie-breaking rules. $\endgroup$– Yuval FilmusDec 27, 2015 at 0:17
-
2$\begingroup$ Your new example doesn't look like an NFA at all. $\endgroup$– Yuval FilmusDec 27, 2015 at 0:18
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
It doesn't decide. Nondeterminism isn't intended to be a realistic model of computation. Check the definition: a nondeterministic automaton accepts if there's any valid sequence of transitions that reach an accepting state.
answered Dec 27, 2015 at 0:09
$\begingroup$
$\endgroup$
3
NFA
The nondeterminism arises from the fact that there are multiple choices for possible next states due to multiple edges for the same input and epsilon ($\epsilon$) transitions. There is no sensor that indicates which state is actually chosen.
The interpretation often given in the theory of computation is that when there are multiple choices, the machine clones itself and one copy runs each choice. It is like having multiple universes in which each different possible action of nature is occurring simultaneously. If there are no outgoing edges for a certain combination of state and input, then the clone dies.
-
3$\begingroup$ Actually, I've never seen the "cloning" interpretation presented as anything other than an informal intuition. The formal definition is always in terms of the existence of an accepting path. $\endgroup$ Dec 27, 2015 at 8:52
-
$\begingroup$ just go through this, Hope it will help you : planning.cs.uiuc.edu/node558.html $\endgroup$ Dec 27, 2015 at 19:38
-
$\begingroup$ Cloning Interpretation is mentioned here too : internetnotes.in/toc .I have posted the sources, I hope my answer is justifiable now and if not please do let me know,Thanks $\endgroup$ Dec 27, 2015 at 19:42