0

If I have a two regular expressions, and want to check whether these two expressions are equivalent, how can it be done?

By "equivalence", I mean do the two regular expressions match exactly the same set of strings?

For example, these two regular expressions are equivalent: 

b{1}b{0,} == bb*

These two are not.

b != bb*

An answer with code in Python would be ideal.

Benjamin Hodgson
  • 42,952
  • 15
  • 108
  • 157
user4629038
  • 89
  • 1
  • 7
  • Could you be a bit more clear , please ? I don't understand. – Onilol Oct 20 '15 at 13:49
  • @Onilol i believe, based on the example OP gave, that OP wants to check if two arbitrary regular expressions produce the same result set. In their case, `b{1}b{0,} == bb*` this would be true and `b{2}b{2,} == bb+` would not. – d0nut Oct 20 '15 at 13:52
  • I wouldn't expect this to be decidable in general but would be very interested to read a full analysis – Benjamin Hodgson Oct 20 '15 at 13:54

1 Answers1

0

I don't believe there is a easy, fast way to do this in python but you can certainly build a function to do this. A post from the computer science stack exchange has a detailed explanation on a 4 step process on how to determine whether or not 2 regular expressions are equivalent.

Community
  • 1
  • 1
d0nut
  • 2,835
  • 1
  • 18
  • 23