Formal Regular Expressions is a Python-based application that parses formal regexes, displaying some of the strings that the regular expression accepts, if the regular expression accepts any given string, and if two regular expressions are equivalent.
All functionality on the website: https://ronit127.github.io/formal-regular-expressions/
Checks if any regex (on top) matches a user-inputted string. This is done by converting the regex into an NFA and then simulating the string on the NFA.
Checks if any two regex are equivalent - that is, they describe the same languages. This is done with the following steps:
- using Thompson's construction algorithm to convert the two regexes into NFAs
- using powerset construction to convert the two NFAs into corresponding DFAs, D1 and D2
- checking DFA equivalence: Creating a product construction of D1 and D2 - let's call D.
- using a depth-first search on D to check if a path exists from the start state to any state such that D1 is accepting and D2 is not accepting or vice versa. If there is, then return FALSE. TRUE otherwise.
Displays some of the strings in the language described by some regex. This is done by accumulating a list of accepted strings when simulating the regex's corresponding NFA.
Any pull requests or suggestions are welcome. If there are any serious bugs, open an issue!