TransWikia.com

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

Computer Science Asked by Prms on December 14, 2020

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?

One Answer

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.

enter image description here

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.

Answered by tylerhx111 on December 14, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP