[Overview] [Previous] [Next]

State-Set Implementation of NFAs

Another way to implement an NFA is to keep either a state set or a bit vector of all the states that the NFA could be in at any given time. Implementation is easier if you use a bit-vector approach (v[i] is True iff state i is a possible state), since most languages provide vectors, but not sets, as a built-in datatype. However, it's a bit easier to describe the algorithm if you use a state-set approach, so that's what we will do. The logic is the same in either case.

function nfa (state set A) returns Boolean:
   local state set B, state a, state b, state c, symbol x;

   for each a in A do
      for each  transition from a
        to some state b do
           add b to B;
   while there is a next symbol do
      { read next symbol (x);
        B := ;
        for each a in A do
          { for each  transition from a to some state b do
                 add b to B;
            for each x transition from a to some state b do
               add b to B;
          }
        for each  transition from
           some state b in B to some state c not in B do
              add c to B;
        A := B;
      }
   if any element of A is a final state then
      return True;
   else
      return False;