[EMAIL PROTECTED] wrote: > 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.
That's right. For finite regular language, you don't allow cycles. That means the graph must be a DAG (directed acyclic graph. If not directed it must be a tree, simple to check as node-count is edge-count plus one). Once you have a DAG, the problem becomes enumerating all paths from root node to any final node. This is a pretty straighforward problem in graph theory. I think you can simply find all from root-node to any other node and discard any of the path ending in a non-final state node. Karthik > > 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. > > Cheers, > -Blair -- http://mail.python.org/mailman/listinfo/python-list
