Class NFA

  • public class NFA
    extends Object
    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 reluctant modifiers, and other features in industrial-strength implementations such as Pattern and Matcher.

    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.

    For additional documentation, see Section 5.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • NFA

        public NFA​(String regexp)
        Initializes the NFA from the specified regular expression.
        regexp - the regular expression
    • Method Detail

      • recognizes

        public boolean recognizes​(String txt)
        Returns true if the text is matched by the regular expression.
        txt - the text
        true if the text is matched by the regular expression, false otherwise
      • main

        public static void main​(String[] args)
        Unit tests the NFA data type.
        args - the command-line arguments