edu.princeton.cs.algs4

Class NFA

java.lang.Object

edu.princeton.cs.algs4.NFA

public class NFA
extends java.lang.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 relucantant 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 Summary

Constructors

Constructor and Description
NFA(java.lang.String regexp) Initializes the NFA from the specified regular expression.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Unit tests the NFA data type.
boolean	recognizes(java.lang.String txt) Returns true if the text is matched by the regular expression.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NFA

public NFA(java.lang.String regexp)

Initializes the NFA from the specified regular expression.

Parameters:

regexp - the regular expression

Method Detail

recognizes

public boolean recognizes(java.lang.String txt)

Returns true if the text is matched by the regular expression.

Parameters:

txt - the text

Returns:

true if the text is matched by the regular expression, false otherwise

main

public static void main(java.lang.String[] args)

Unit tests the NFA data type.

Parameters:

args - the command-line arguments