Determine if two regular expressions are equivalent.
In theory, the equivalence problem for regular expressions is Turing-decidable.
- Convert both regular expressions into equivalent NFAs
- Convert both of these NFAs into equivalent DFAs
- Construct a new DFA such that its language is the symmetric difference of the languages of the two DFAs
- Check if none of the reachable states in the newly constructed DFA are accepting states
The primary purpose of this program is to demonstrate computational theory as it applies to regular languages; any regard for efficiency is secondary.