How does the NFA decide in a state where there are multiple equally valid "next states"?
How does it decide on which state it takes to with 1?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.