In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Question

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the symbol 0. Does this mean the computation dies, or does this mean that the string is accepted?

Answer 1

A string is accepted by an NFA if there is a sequence of moves such that it can reach a final state at the end of the string.

As you said, assume that for $w=0110$ after reading $011$ we are in a final state (called $q$) and there is no transition like $\delta(q,0)$, this is when we encounter a situation called dead configuration. At this point we can't just say the machine stops, because it's not precise. What we can say here is that no final state can be reached by reading $w$ so the NFA doesn't accept the string.

Answer 2

Finite automatas (either) DFA or NFA, must be process the entire input string.

DFAs will keep track of a single state while processing a string. Think of it as a pointer to the current state. It will transition (i.e. move that pointer) according to its rules while processing a string. Remember that for a DFA, all states must have a transition for each symbol in the alphabet. Thus, the DFA will have a unique path to the final state after processing the entire input string. If final state is an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.

NFAs on the other hand will keep track of a set of states while processing a string. Think of it as having a set of pointers to all possible states for which the NFA could have transitioned to after processing a certain number of symbols. This allows for the NFA to not have all transitions defined, the inclusion of $\epsilon$ on transitions, and having a symbol on more than one transition out of a state. If the set of states contains an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.

Take the following example:

$L = \{0,1\}^*00^+1 + \{0,1\}^*01^+0$. The following NFA accepts this language.

We can make a chart that shows how the NFA will process an input string. The left column indicates the current set of states (when we start processing we start with {A}). The middle column is the set of states possible from the current set of states after processing a 0, and similarly for the right column with 1.

              0         1
_________ | ________ | _______
{A}       | {A,B,C}    {A}
{A,B,C}   | {A,B,C,D}  {A,C,D}
{A,B,C,D} | {A,B,C,D}  {A,C,D}
{A,C,D}   | {A,B,C,D}  {A,C}
{A,C}     | {A,B,C,D}  {A,C}

Suppose we have an input string 001. The NFA will process the input:

0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}

We see that the final set of states is {A,B,C,D} which does contain an accepting state. Thus, $001 \in L$. Notices while processing the string, the NFA did not record the way it got to the accepting state; it just records that it is possible to get to one.

Suppose however we have an input string of 0011. The NFA will process the input:

0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}
1 from {A,C,D}   -> {A,C}

We see then that the final set of states is {A,C} which does not contain an accepteing state. Thus, $0011 \notin L$.

TL;DR

FAs must process the entire input. For NFAs, if the final set of possible state the machine could end in contains a final state, then the input string is accepted; otherwise, it is rejected.