2.2.5 Using an NFSA to Accept Strings

If we want to know whether a string is an instance of sheeptalk or not, and if we use a non-deterministic machine to recognize it, we might follow the wrong arc and reject it when we should have accepted it. That is, since there is more than one choice at some point, we might take the wrong choice. This problem of choice in non-deterministic models will come up again and again as we build computational models, particularly for parsing. There are three standard solutions to the problem of non-determinism:

LOOK-AHEAD

• Backup: Whenever we come to a choice point, we could put a marker to mark where we were in the input, and what state the automaton was in. Then if it turns out that we took the wrong choice, we could back up and try another path.

Look-ahead: We could look ahead in the input to help us decide which path to take.

PARALLELISM

Parallels: Whenever we come to a choice point, we could look at every alternative path in parallel.

We will focus here on the backup approach and defer discussion of the look-ahead and parallelism approaches to later chapters.

The backup approach suggests that we should blithely make choices that might lead to deadends, knowing that we can always return to unexplored alternative choices. There are two keys to this approach: we need to remember all the alternatives for each choice point, and we need to store sufficient information about each alternative so that we can return to it when necessary. When a backup algorithm reaches a point in its processing where no progress can be made (because it runs out of input, or has no legal transitions), it returns to a previous choice point, selects one of the unexplored alternatives, and continues from there. Applying this notion to our non-deterministic recognizer, we need only remember two things for each choice point: the state, or node, of the machine that we can go to and the corresponding position on the tape. We will call the combination of the node and position the search-state of the recognition algo

rithm. To avoid confusion, we will refer to the state of the automaton (as opposed to the state of the search) as a node or a machine-state. Figure 2.21 presents a recognition algorithm based on this approach.

Before going on to describe the main part of this algorithm, we should note two changes to the transition table that drives it. First, in order to represent nodes that have outgoing $ \varepsilon $-transitions, we add a new $ \varepsilon $-column to the transition table. If a node has an $ \varepsilon $-transition, we list the destination node in the $ \varepsilon $-column for that node's row. The second addition is needed to account for multiple transitions to different nodes from the same input symbol. We let each cell entry consist of a list of destination nodes rather than a single node. Fig. 2.20 shows the transition table for the machine in Figure 2.18 (NFSA #1). While it has no $ \varepsilon $-transitions, it does show that in machine-state $ q_2 $ the input a can lead back to $ q_2 $ or on to $ q_3 $.

Fig. 2.21 shows the algorithm for using a non-deterministic FSA to recognize an input string. The function ND-RECOGNIZE uses the variable agenda to keep track of all the currently unexplored choices generated during the course of processing. Each choice (search state) is a tuple consisting of a node (state) of the machine and a position on the tape. The variable current-search-state represents the branch choice being currently explored.

ND-RECOGNIZE begins by creating an initial search-state and placing it on the agenda. For now we don't specify what order the search-states are placed on the agenda. This search-state consists of the initial machine-state of the machine and a pointer to the beginning of the tape. The function NEXT is then called to retrieve an item from the agenda and assign it to the variable current-search-state.

As with D-RECOGNIZE, the first task of the main loop is to determine if the entire contents of the tape have been successfully recognized. This is done via a call to ACCEPT-STATE?, which returns accept if the current search-state contains both an accepting machine-state and a pointer to the end of the tape. If we're not done, the machine generates a set of possible next steps by calling GENERATE-NEW-STATES, which creates search-states for any $ \varepsilon $-transitions and any normal input-symbol transitions from the transition table. All of these search-state tuples are then added to the current agenda.

Finally, we attempt to get a new search-state to process from the agenda. If the agenda is empty we've run out of options and have to reject the input. Otherwise, an unexplored option is selected and the loop continues.

It is important to understand why ND-RECOGNIZE returns a value of reject only when the agenda is found to be empty. Unlike D-RECOGNIZE, it does not return reject

when it reaches the end of the tape in a non-accept machine-state or when it finds itself unable to advance the tape from some machine-state. This is because, in the non-deterministic case, such roadblocks only indicate failure down a given path, not overall failure. We can only be sure we can reject a string when all possible choices have been examined and found lacking.

Figure 2.22 illustrates the progress of ND-RECOGNIZE as it attempts to handle the input baaa!. Each strip illustrates the state of the algorithm at a given point in its processing. The current-search-state variable is captured by the solid bubbles representing the machine-state along with the arrow representing progress on the tape. Each strip lower down in the figure represents progress from one current-search-state to the

next.

Little of interest happens until the algorithm finds itself in state $ q_2 $ while looking at the second a on the tape. An examination of the entry for transition-table[ $ q_{2,a} $] returns both $ q_2 $ and $ q_3 $. Search states are created for each of these choices and placed on the agenda. Unfortunately, our algorithm chooses to move to state $ q_3 $, a move that results in neither an accept state nor any new states since the entry for transition-table[ $ q_3 $, a] is empty. At this point, the algorithm simply asks the agenda for a new state to pursue. Since the choice of returning to $ q_2 $ from $ q_2 $ is the only unexamined choice on the agenda it is returned with the tape pointer advanced to the next a. Somewhat diabolically, ND-RECOGNIZE finds itself faced with the same choice. The entry for transition-table[ $ q_{2,a} $] still indicates that looping back to $ q_2 $ or advancing to $ q_3 $ are valid choices. As before, states representing both are placed on the agenda. These search states are not the same as the previous ones since their tape index values have advanced. This time the agenda provides the move to $ q_3 $ as the next move. The move to $ q_4 $, and success, is then uniquely determined by the tape and the transition-table.