Regular expression/NFA membership test

Contributors

• Jorge Calderon
• Garret Mook
• Katie Pell

Usage

main.py

Input

A regular expression R

The following regular expression conventions are recognized by this program:
• The only input characters permitted are lowercase letters a-z and numeric digits 0-9
• Parentheses may be used to manipulate order of operation
• Epsilon is represented using the symbol E
• A union is represented by the symbol +
• The Kleene star is represented by the standard symbol *
• Concatenation is represented by the symbol .
  Note: implicit concatenation is not permitted, i.e. "aba" should be written as a.b.a

A string w

Task

1. Convert the regular expression R to an epsilon-NFA M₁.
2. Remove epsilon transitions to obtain epsilon-free NFA M₂.
3. Test if the string w is accepted by the epsilon-free NFA M₂.

Output

True/false: Whether or not the string w is the in the language of the regular expression R, i.e. if w is in L(R).