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;

Copyright © 1996 by David Matuszek

Last modified Jan 29, 1996