Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <bvr01iFu926U1@mid.individual.net>
References: <bvr01iFu926U1@mid.individual.net>
Date: Wed, 11 Jun 2014 20:09:07 +0200
Subject: Re: Python's re module and genealogy problem
From: Vlastimil Brom <vlastimil.brom@gmail.com>
To: python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.11018.1402510564.18130.python-list@python.org>
Lines: 40
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:73185

2014-06-11 14:23 GMT+02:00 BrJohan <brjohan@gmail.com>:
> For some genealogical purposes I consider using Python's re module.
>...
>
> Now, my problem: Is there a way to decide whether any two - or more - of
> those regular expressions will match the same string?
>
> Or, stated a little differently:
>
> Can it, for a pair of regular expressions be decided whether at least one
> string matching both of those regular expressions, can be constructed?
> --
> https://mail.python.org/mailman/listinfo/python-list

Hi,
i guess, you could reuse some available generators for strings
matching a given regular expression, see e.g.:
http://stackoverflow.com/questions/492716/reversing-a-regular-expression-in-python/
for example a pyparsing recipe:
http://stackoverflow.com/questions/492716/reversing-a-regular-expression-in-python/5006339#5006339

which might be general enough for your needs - of course, you cannot
use unbound quantifiers, backreferences, etc.

Then you can test for identical strings in the generated outputs -
e.g. using the set(...) and its intersection method.

You might also check a much more powerful regex library
https://pypi.python.org/pypi/regex

which, beyond other features, also supports the mentioned fuzzy matches, cf.

>>> regex.findall(r"\bSm(?:ith){e<3}\b", "Smith Smithe Smyth Smythe Smijth")
['Smith', 'Smithe', 'Smyth', 'Smythe', 'Smijth']
>>>
(but, of course, you will have to be careful with this feature in
order to reduce false positives)

hth,
   vbr