A string is accepted by an nfa if there is some sequence of possible moves
that will put the machine in a final state at the end of the string. A string is
rejected (that is, not accepted) only if there is no possible sequence of moves by
which a final state can be reached. Nondeterminism can therefore be viewed as
involving “intuitive” insight by which the best move can be chosen at every state
(assuming that the nfa wants to accept every string).
Example 2.7
Consider the transition graph in Figure 2.8. It describes a nondeterministic
accepter since there are two transitions labeled a out of q 0 .
Figure 2.8
Example 2.8
A nondeterministic automaton is shown in Figure 2.9. It is nondeterministic not
only because several edges with the same label originate from one vertex, but
also because it has a λ-transition. Some transitions, such as δ (q 2 ,0), are
unspecified in the graph. This is to be interpreted as a transition to the empty set,
that is, δ (q 2 ,0) = Ø. The automaton accepts strings λ, 1010, and 101010, but not
110 and 10100. Note that for 10 there are two alternative walks, one leading to
q 0 , the other to q 2 . Even though q 2 is not a final state, the string is accepted
because one walk leads to a final state.
Figure 2.9