I talked with the guy who wrote the ZZ comparator.

"""I can give you the source code under the GPL if you like. However, I  
think it would be difficult to port to python. It's 1100 lines of  
very SML-style mostly-uncommented code. Do you know SML?

It's available at svn://mlton.org/mltonlib/trunk/ca/terpstra/regexp.  
I would expect credit for the algorithm. :-) Let me know if you  
succeed in porting it."""

I don't know any SML though.
If anybody does or can write a python equaliant of the algorithm:

"""1. Parse the regular expression (in GNU regular expression syntax)
2. Convert that parse tree into an NFA
3. Convert the NFA into a DFA by an algorithm I invented (it's why I
wrote this program; I thought of the algorithm and found it amusing
to see it in action)

For comparing regular expressions I take the following additional  
steps
4. Combine the two DFA's (with the cross product)
4a. For finding common words, I intersect them
4b. For finding words in A, but not B, I intersect A with the negated
DFA of B
4c. ...
5. Find the minimal DFA corresponding to this intersection
6. Run a weighted depth-first search (similar to Dijkstra's) to find
the least-weighted path from the initial state to an accepting state
(the weighting makes it prefer human readable characters in the
examples)"""

It could be cool.
Otherwise I can also try to learn sml and port it.