Going in a slightly different direction ... There has been lots of published work on how to create efficient FSMs from regexps. Generally these FSMs are used for pattern matching (i.e. "does string 's' match regexp 'e'?").
Is there any corresponding literature on the topic addressed by the OP's challenge of generating the languaged defined by a regexp (or the complement of that regexp)? --jfc -- http://mail.python.org/mailman/listinfo/python-list
