Package jpaul.RegExps

Classes that model regular expressions and NFAs.

See:
Description

Interface Summary

NFA.BigState<State>

Certain NFA transformations (ex: NFA.simplify()) produce NFAs whose states are sets of original states.

Class Summary

NFA<State,A>	NFA models a Non-deterministic Finite Automaton.
RegExp<A>	RegExp models a regular expression.
RegExp.Atomic<A>	Regular expression that matches only the 1-length string consisting of exactly one specific symbol.
RegExp.Concat<A>	Regular expression produced by concatenating two regular expressions.
RegExp.EmptyStr<A>	Regular expressions that matches only the empty string.
RegExp.None<A>	Regular expression that does not match any string.
RegExp.Star<A>	The star regular expression.
RegExp.Union<A>	The regular expression that matches any string matched by at least one of two specific regular expression.
RegExp.Visitor<A,Res>	Instance of the visitor pattern for RegExps.

Package jpaul.RegExps Description

Classes that model regular expressions and NFAs.

Most of the RegExp-related packages are focused on efficiently parsing strings of characters; they usually take a regular expression and convert it into an NFA (a Non-deterministic Finite Automaton) and later into a DFA (a Deterministic Finite Automaton) that is used for parsing.

Instead, this package offers classes that are parametric in the input alphabet. Currently, the focus is on converting an NFA into a regular expression, but ultimately, we plan to cover the other direction too.

Where to start?

• Regular expressions: RegExp and its inner classes.
• Finite automata: NFA.

Future plans:

• RegExp 2 NFA conversion
• NFA 2 DFA conversion
• Finite automata equivalence, difference, intersection etc.

Author:

Suhabe Bugrara - suhabe@alum.mit.edu, Alexandru Salcianu - salcianu@alum.mit.edu