How does the following Non Deterministic Automata accept the language A every time?

Question

So I am starting out with automata theory and I was reading a book and came across an example where the author tries to explain what exactly Nondeterministic Finite Automatas (NFAs) are. He gave an example of a language A such that:

$A = \{w \in \{0,1\}^*: w \text{ has a 1 in the third position from the right}\}$

He then constructs a NFA which is:

Now how he explained it is that the NFA "guesses" that the 1 is the third from right in the string and then it "verifies" that there are exactly two symbols remaining. If there are more than two remaining symbols, then the NFA hangs (in state $q_1$) after having read the next two symbols.

Now I don't know a lot about this topic, but from what I understand an automata can read a string only once. Also, the automata can proceed in either of the two options it has. So how is it that it will accept the string every time? Maybe some time it just stays on $q_1$ and never decides to go to $q_2$. Or maybe it goes to $q_2$ too early and hangs even though there is a 1 in third position from right.

It seems random, but the author mentions nothing about this. So I'm guessing I'm wrong.

Please someone point out what I'm not understanding right here.

Answer 1

… the automata can proceed in either of the two options it has.

Well, yes. But for a Non-Deterministic Automaton, that means that it proceeds with both options. At the same time. It can do that precisely because it is non-deterministic.

Some people like to describe that fanciful references to time travel, psychic precognition (infallible oracles), or alternative realities, but no such violation of the rules of the physical universe is necessary in the case of Non-deterministic Finite State Automata.

No matter how much reality branching the machine does, the active possibilities are all in a subset of the set of states. In other words, we could easily produce a Deterministic FA whose states are precisely the elements of the power set of the set of states of the NFA, and in fact that is precisely what is done by real-life practical software. (Except that only reachable states are included, so the size of the DFA is often much smaller than exponential in the size of the NFA.)

Answer 2

The automaton is non-deterministic because there are two transitions from state $q_1$ with input $1$, one is $q_1$ and the other is $q_2$. After moving to $q_2$, the transitions are deterministic to $q_3$ and then to $q_4$. Thus the assertion is correct.

Answer 3

Let us view a NFA as a graph. A path in this graph is called successful if it starts in some initial state and ends up in some final state. Now a word $w$ is accepted by the NFA if and only if there exists a successful path with label $w$.

This quantifier "there exists" is the crucial point. In particular, a word $w$ can be the label of several paths, some of which are successful, some other ones are not. But if at least one is successful, then $w$ accepted. Dually, $w$ is rejected if and only if no path with label $w$ is successful.