---------------------------------------------------------------- Assignment 3b. Modifying the NDFA algorithm ---------------------------------------------------------------- As we saw in Problem 3.a.1, there is a problem with the simple depth-first search algorithm in some graphs. The same problem extends to our first-pass algorithm for simulating an NDFA. Problem 3.b.1 [5 points] Under exactly what circumstances might the problem appear when simulating an NDFA? Problem 3.b.2 [10 points] The first-pass algorithm appears below. Modify it to solve the problem, using the same approach taken in Problem 3a.2 (note that you are not implementing the solution, so the changes can be in English, not LISP!). (You might find it useful to simulate on paper the algorithm running on the example NDFA below, with input '(a b a a c).) Turn in the modified algorithm. ---------------------------------------------------------------- First-pass Algorithm for simulating an NDFA ---------------------------------------------------------------- Given an NDFA, M, consisting of [Alphabet,States,Initial,Final,Transitions], and a string of input symbols, S: set current-state to Initial(M) set input-length to length(S) set possibilities to singleton list ([current-state,1]) while possibilities is not empty { set [state,loc] to pop(possibilities) if (state is a member of Final(M) AND loc == input-length + 1) Accept and terminate set input-symbol to the Nth symbol of S (numbering from 1) set transitions to the list of Transitions(M) departing state on input-symbol add (to transitions) any epsilon transitions in Transitions(M) departing state for each transition [source,symbol,destination] in transitions { if symbol is EPSILON add configuration [destination,loc] to possibilities else add configuration [destination,loc+1] to possibilities } } Reject and terminate ---------------------------------------------------------------- Example NDFA: Alphabet (a b c) States (q0 q1 q2)) Initial q0 Final (q1) Transitions ([q0, a, q1] [q1, epsilon, q2] [q1, b, q0] [q2, epsilon, q1] [q2, a, q0] [q2, c, q2])

Return to the course home page.