The NFA class provides a data type for creating a Nondeterministic finite state automaton (NFA) from a regular expression and testing whether a given string is matched by that regular expression. It supports the following operations: Concatenation, Closure, Binary or, and Parentheses. It does not support Mutiway or, Character classes, Metacharacters (either in the text or pattern), Capturing capabilities, Greedy or Relucantant modifiers, and other features in industrial-strength implementations such as Regexand Match.

This implementation builds the NFA using a digraph and a stack and simulates the NFA using digraph search (see the textbook for details). The constructor takes time proportional to M, where M is the number of characters in the regular expression. The Recognizes method takes time proportional to M N, where N is the number of characters in the text.