Assignment 3b, Ling 645/CMSC 723, Fall 1997

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
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
       add configuration [destination,loc+1] to possibilities
Reject and terminate

Example NDFA:

  Alphabet      (a b c)
  States        (q0 q1 q2))
  Initial       q0
  Final         (q1)
		 ([q0, a, q1]
		  [q1, epsilon, q2]
		  [q1, b, q0]
                  [q2, epsilon, q1]
                  [q2, a, q0]
		  [q2, c, q2])

Return to the course home page.