Python's re module and genealogy problem

[Thomas Rachel]

Am 11.06.2014 14:23 schrieb BrJohan:

> Can it, for a pair of regular expressions be decided whether at least
> one string matching both of those regular expressions, can be constructed?
>
> If it is possible to make such a decision, then how? Anyone aware of an
> algorithm for this?

Just a feeling-based statement: I don't think that is easily possible.

Every RE can potentially match an infinite number of statements.

Just have a look at

re1 = re.compile('A43.*')
re2 = re.compile('.*[0-9][A-F]')

It can easily seen that the area these REs work on is different; they 
are orthogonal.

So there is an infinite number of strings these REs match.


Thomas