EXAMPLE 1.38 Recall the NFA Ni: 0,1 0,1 0,e 91 (2 93 94 he formal description of N1 is (Q, , , q1, F), where 1. Q = {q1-2.93.94), 2. = {0,1), 3. is given as 1) 1,920 4. qi is the start state, and The formal definition of computation for an NFA is similar to that for a DFA. Let N = (Q, , , q0, F) be an NFA and w a string over the alphabet . Then we say that N accepts w if we can write w as w = yiy2 ym, where each yi is a member of Ee and a sequence of states ro,r,..., Tm exists in Q with three conditions: 1. roo, 2. ri+1 E (ri,yi+1), for i=0, ,m-1, and Condition 1 savs that the machine starts out in the start state. Condition 2 says that state ri+1 is one of the allowable next states when N is in state rj and reading Vi+1 . Observe that (ri, yi+1 ) 1s the set of allowable next states and so we say that ri+1 is a member of that set. Finally, condition 3 says that the machine accepts its input if the last state is an accept state