Suppose I give you two arbitrary regular expressions. Are they equivalent?
Does there exist an algorithm to determine whether two regexes are
equivalent? What complexity class does this algorithm live in? What does
"equivalent" even mean in this context? What about if one expression
matches a subset of the other? Or a superset? Or in general two
partially-overlapping sets?
