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