3
$\begingroup$

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

Such as here:

enter image description here

How does it decide on which state it takes to with 1?

$\endgroup$
  • $\begingroup$ Or perhaps this implies to always convert to the equivalent DFA? $\endgroup$ – mavavilj Dec 27 '15 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 Filmus Dec 27 '15 at 0:07
  • 1
    $\begingroup$ Then nothing special happens. It still tries all legal trajectories. $\endgroup$ – Yuval Filmus Dec 27 '15 at 0:10
  • 1
    $\begingroup$ @mavavilj Then it's probably deterministic, or has explicit tie-breaking rules. $\endgroup$ – Yuval Filmus Dec 27 '15 at 0:17
  • 2
    $\begingroup$ Your new example doesn't look like an NFA at all. $\endgroup$ – Yuval Filmus Dec 27 '15 at 0:18
10
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 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$ – David Richerby Dec 27 '15 at 8:52
  • $\begingroup$ just go through this, Hope it will help you : planning.cs.uiuc.edu/node558.html $\endgroup$ – Jatin Khattar Dec 27 '15 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$ – Jatin Khattar Dec 27 '15 at 19:42

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.