# 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? – mavavilj 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. – Yuval Filmus Dec 27 '15 at 0:07
• Then nothing special happens. It still tries all legal trajectories. – Yuval Filmus Dec 27 '15 at 0:10
• @mavavilj Then it's probably deterministic, or has explicit tie-breaking rules. – Yuval Filmus Dec 27 '15 at 0:17
• Your new example doesn't look like an NFA at all. – Yuval Filmus Dec 27 '15 at 0:18

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.