I'm currently working on "regular expression" exercises in the textbook ("An Introduction to Formal Languages and Automata"), and the problem that I'm facing is, most of the time, my solution is different than the book's ones. However, I realize that they could both express the same language, but I couldn't find a way to prove it. I wonder if is there a mathematical way (like induction) to prove that the two regular expression are actually identical? Any suggestion?
Thank you,
Best Answer
That's an extremely difficult problem. You could convert the regular expression to a DFA and minimize it, but that's PSPACE-complete...
I think procedures for determining equivalence for regular expressions is known to take at least exponential space and time and at most double exponential time, but I could be wrong.