----------------------------------------------------------------
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])