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
[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
else
}
}
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])

```