I am having a really hard time understanding NFAs as opposed to DFAs. I have a few questions about how they work.

Question

Deterministic Finite Automata make perfect sense to me. They are essentially a flowchart and cover every possible input and transition from and to each state. Non-Deterministic Finite Automata, on the other hand, completely bewilder me. I don't understand how they work. How do you, the reader, know when they make a transition? When there are two or more options for a given input, which do you pick? When there are no options for the given input, does it automatically go to a hidden, permanent reject state? What if it was in an accept state? What if it was in a reject state, read some input it didn't have a transition for, and then read some input it did have a transition for? Does this count? Could someone help me make sense of these? Thanks.

Answer 1

One way to think about NFAs is to imagine them making all possible transitions at each input, so that an NFA can be in several different states at the same time. When the entire input has been read, look at the states that the NFA is in. If at least one of them is an acceptor state, the NFA accepts the word; if none of them is an acceptor state, then it rejects the word.

If there are no transitions for a given input, the NFA comes to a screeching, grinding halt: that input simply cannot be processed in that state. It’s almost as if the input had broken the machine. Understandably enough if you think of that way, the offending word is not accepted; whether or not the machine was in an acceptor state at the time makes no difference. Similarly, any remaining input makes no difference.

What happens if the NFA is in states $q_1$ and $q_2$ reading an input $a$, and there is an $a$-transition from $q_1$ but not from $q_2$? In that case the machine halts the track running through $q_2$ but continues processing along the track running through $q_1$. Thus, it’s still possible that the input might end up being accepted. Thus, what I said in the last paragraph isn’t quite true: it isn’t the whole machine that comes to a halt, but only the computation along the path that’s blocked by the absence of the needed transition. If neither of the states $q_1$ and $q_2$ has an outgoing $a$-transition, however, both of the ongoing computations would be blocked: the whole computation would come to a halt unfinished, and the input word would be rejected.

There’s one other aspect of NFAs that often causes some trouble: $\epsilon$-transitions. If there is an $\epsilon$-transition from state $q_1$ to state $q_2$, the NFA can make the transition from $q_1$ to $q_2$ spontaneously, without reading any input at all. Thus, the moment it reaches $q_1$ in some computation, it’s automatically in $q_2$ as well.

The alternative view is to consider computations that proceed through one state at a time, but to consider all possible computations driven by the given input string. Any given computation may come to a halt prematurely, if it reaches a state that has no outgoing transition for the next input symbol to be read. Throw out those incomplete computations and look only at the complete ones, if there are any. If at least one complete computation ends up in an acceptor state, the input is accepted; if none of them ends up in an acceptor state, it’s rejected.