Project Overview

CP1: NFA Simulator

Using graph algorithm to simulate NFAs.

Input: NFA file, target string

Output: Accept/Reject, path (if accepted)

Example:

Usage:

CP2: Regular Expression Simulator

Parse regular expressions (only with '(', ')', '|', '*') with PDA, construct a tree. Then convert the tree into NFA.

Input: regexp, lines of strings

Output: strings that match the regexp

Example:

CP3: Sed Simulator

Add group to the regexp parser to simulate the mini-sed (msed). Prove msed is Turing-Complete by implementing a translation from Turing machines to msed.

Example:

Usage:

CP4: Regular Expression Matcher with Backreferences

Add backreference to the regexp parser.

Prove regexp with backreferences is NP-Complete by reducing it into SAT problem in polynomial time

Usage:

Language and Libraries

• Language: Python
• Standard Libraries Used: All standard libraries except re