# How does the NFA decide in a state where there are multiple equally valid "next states"?

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?

• Or perhaps this implies to always convert to the equivalent DFA? Dec 27 '15 at 0:03
• It doesn't decide. It tries all legal trajectories, and accepts if at least one of them ends at an accepting state. Dec 27 '15 at 0:07
• Then nothing special happens. It still tries all legal trajectories. Dec 27 '15 at 0:10
• @mavavilj Then it's probably deterministic, or has explicit tie-breaking rules. Dec 27 '15 at 0:17
• Your new example doesn't look like an NFA at all. Dec 27 '15 at 0:18

## 2 Answers

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.

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.

• 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. Dec 27 '15 at 8:52
• just go through this, Hope it will help you : planning.cs.uiuc.edu/node558.html Dec 27 '15 at 19:38
• 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 Dec 27 '15 at 19:42