[Overview] [Previous] [Next]

Recursive Implementation of NFAs

An nfa can be implemented by means of a recursive search from the start state for a path (directed by the symbols of the input string) to a final state.

Here is a rough outline of such an implementation:

function nfa (state A) returns Boolean:
    local state B, symbol x;
    for each  transition from state A to some state B do
        if nfa (B) then return True;
    if there is a next symbol then
        { read next symbol (x);
          for each x transition from state A to
            some state B do
                if nfa (B) then
                    return True;
          return False;
        }
    else
        { if A is a final state then return True;
          else return False;
        }

One problem with this implementation is that it could get into an infinite loop if there is a cycle of

transitions. This could be prevented by maintaining a simple counter (How?).