0

Is there a quick script/tool to check if two regular expressions are equal? For example: I want to know if 0*(01 + 11) is equal to (0*01 + 0*11) i.e. Can I multiply them just as basic math?

user963241
  • 649
  • 1
    Yes, these two are equivalent, and yes, $\sigma(\tau+\rho)=\sigma\tau+\sigma\rho$ for regular expressions $\sigma,\tau,\rho$. There is an algebra of regular expressions; some of it, like the bit that you used here, is very straightforward. Dealing with the Kleene star can get a little more complicated, however. – Brian M. Scott May 07 '16 at 15:13
  • For arbitrary regexes, the idea is to first convert each to a DFA: http://cs.stackexchange.com/questions/12267/algorithm-to-determine-whether-two-regexes-are-equivalent – parsiad May 07 '16 at 15:16

0 Answers0