Enumerating Regular Expressions

blair.bethwaite at gmail.com blair.bethwaite at gmail.com
Tue May 9 01:03:27 EDT 2006

James Stroud wrote:
> You see the difficulty don't you? How will the computer know in advance
> that the regex matches only a finite set of possible strings?

Well sure it might be a little difficult to figure _that_ out, although
probably not all that hard if you converted to an FSA or something.  I
imagine detecting looping would be as simple as applying the right
graph algorithm.

But that's not the point, you don't strictly need to know in advance
whether the regex represents a finite or infinite language.  I just
want to enumerate it, if it's going to take longer than the life of the
universe and a stack size to match to do it, then so be it.  It's
surely up to the user to be careful about how they form their
expressions.  One way to get around it would be to disallow the *
operator in enumerations.


More information about the Python-list mailing list