Q:

Distance between regular expression

Can we compute a sort of distance between regular expressions ? 
The idea is to mesure in which way two regular expression are similar. 

A:

You can build deterministic finite-state machines for both regular expressions and compare the transitions.  The difference of both transitions can then be used to measure the distance of these regular expressions. 

A:

There are a few of metrics you could use:

The length of a valid match.  Some regexs have a fixed size, some an upper limit and some a lower limit.  Compare how similar their lengths or possible lengths are. 
The characters that match.  Any regex will have a set of characters a match can contain (maybe all characters).  Compare the set of included characters. 
Use a large document and see how many matches each regex makes and how many of those are identical. 

Are you looking for strict equivalence?