Figure 2.9: .An NFA accepting all strings that end in 01

However, if the next symbol is 0, this NFA also guesses that the final 01 has begun. An arc labeled 0 thus leads from qo to state qi. Notice that there are two arcs labeled 0 out of qq. The NFA has the option of goiiig either to qo or to qi, and in fact it does both, as we shall see when we make the definitions precise. In state qi, the NFA checks that the next symbol is 1, and if so, it goes to state q2 and accepts.

Notice that there is no arc out of qi labeled 0, and there are no arcs at all out of 92- In these situations, the thread of the NFAs existence corresponding to those states simply dies, although other tlrreads may continue to exist. While a DFA has exactly one arc out of eacli state for each input symbol, an NFA has no such constraint; we have seen in Fig. 2.9 cases where the number of arcs is zero, one, and two, for example.

Figure 2.10 suggests how an NFA processes inputs. We have shown what happens when the automaton of Fig. 2.9 receives the input sequence 00101. It starts in only its start state, qo- When the first 0 is read, the NFA may go to either state qo or state qj, so it does both. These two threads are suggested by the second column in Fig. 2.10.

Then, the second 0 is read. State qo may again go to both qo and qi. However, state qi has no transition on 0, so it dies. When the third input, a

2.3.1 An Informal View of Nondeterministic Finite Automata

Like ttie DFA, an NFA has a finite set of states, a finite set of input symbols, one start state and a set of accepting states. It also has a transition function, which we shall commonly call S. The difference between the DFA and the NFA is in the type of 6. For the NF.A, 5 is a function that takes a state and input symbol as arguments (like the DFAs transition function), but returns a set of zero, one, or more states (rather than returning exactly one state, as the DFA must). We shall start with an example of an NFA, and then make the definitions precise.

Example 2.6; Figure 2.9 shows a nondeterministic finite automaton, whose job is to accept all and only the strings of Os and Is that end in 01. State qo is the start state, and we can think of the automaton as being in state qo (perhaps among other states) л¥Ьепеуег it has not yet guessed that the final 01 ha.4 begun. It is always possible that the next symbol does not begin the final 01, even if that symbol is 0. Thus, state qo may transition to itself on both 0 and 1.

Start 0

(stuck)

(stuck) 0

Figure 2.10: The states an NFA is in during the processing of input sequence 00101

1, occurs, we must consider transitions from both t/o ajid qi. We find that qo goes only to go on 1, while qi goes only to q. Thus, after reading 001, the NFA is in states qo and 72- Since q2 is an accepting state, the NFA accepts 001.

However, the input is not finished. The fourth input, a 0, causes 172s thread to die, while qo goes to both q and q-y. The last input, a 1, sends qo to qo and qi to q-2. Since we are again in an accepting state, 00101 is accepted. □

2.3.2 Definition of Nondeterministic Finite Automata

Now, let us introduce the formal notions associated with nondeterministic finite automata. The differences between DF.4s and NFAs will be pointed out as we do. An NF.4 is represented essentially like a DFA:

A{Q,-L,S,qo,F)

where:

1. Q is a finite set of states.

2. S is a finite set of input syjnbols.

3. qo, я member of Q, is the start state.

4. F, a subset of Q, is the set of final (or accepting) states.

5. 5, the transition function is a function that takes a state in Q and an input symbol in S as arguments and returns a subset of Q. Notice that the only difference between an NFA and a DFA is in the type of value that 6 returns: a set of states in the case of an NFA and a single state in the case of a DFA.

Example 2.7: The NFA of Fig. 2.9 can be specified formally as

({№,(7i,?:i}!{0:l}t9o.{92})

Figure 2.11: Transition table for an NFA that accepts all strings ending in 01

where the transition function 6 is given by the transition table of Fig. 2.11. □

Notice that transition tables can be used to specify the transition function for an NF.A as well as for a DFA. The only difference is that each entry in the table for the NFA is a set, even if the set is a migleton (has one member). Also notice that when there is no transition at all from a given state on a given input symbol, the proper entry is 0, the empty set.

2.3,3 The Extended Transition Function

As for DFAs, we need to extend the transition function of an NFA to a function 5 that takes a state q and a string of input symbols and returns the set of states that the NFA is in if it starts in state q and processes the string w. The idea was suggested by Fig. 2.10; in essence 5{q,w) is the column of states found after reading if q is the lone state in the first column. For instance. Fig. 2.10 suggests that 5(go, 001) = {qa, q-i}- Formally, we define 5 for an NFAs transition function 5 by:

BASIS; <5(9,e) = {q}. That is, without reading any input symbols, we are only in the state we began in.

INDUCTION: Suppose w is of the form w = xa, where a is the final symbol of w and X is the rest of w. Also suppose that 6{q,x) = {pi,p2,. ,Рк}- Let

У 5(pi,a) = {Г1,Г2,...,Тт}

Then Siq,w) = {т1,Г2, . ,Tm}. Less formally, we compute 5{q,w) by first computing d(q, x), and by then following any transition from any of these states that is labeled a.

Example 2.8: Let us use 6 to describe the processing of input 00101 by the NFA of Fig. 2.9. A summary of the steps is:

1. (ge) = {qo}-

2. ((/o,0) = 5(90,0) =