public class NFA extends Object
NFAclass 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
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.
|Constructor and Description|
Initializes the NFA from the specified regular expression.
|Modifier and Type||Method and Description|
Unit tests the
Returns true if the text is matched by the regular expression.
public NFA(String regexp)
regexp- the regular expression
public boolean recognizes(String txt)
txt- the text
trueif the text is matched by the regular expression,
public static void main(String args)
args- the command-line arguments