Someone posted a question on comp.lang.python asking whether there was a function that enumerates all strings that matches a regular expression. One of the responses compared this question to the Halting Problem:
http://groups.google.com/group/comp.lang.python/msg/dcb5c509954d187e
I wrote a response, but decided not to send it to the list. Instead, I am posting it here:
Just because a problem P reduces to the Halting Problem doesn't mean that P is not computable. It's the other direction that gives you problems: if the Halting Problem reduces to P, then P is not computable. In particular, a regular expression halts on any input.
As for whether the language of a regular expression is finite, I don't imagine it would be that difficult. All you need to do is check whether the * operator is used. This follows from the following lemma:
Let e = e1 (concat|union) e2. L(e) finite iff L(e1) and L(e2) finite.
On the other hand, I would imagine that there's no good way of calculating |L(e)| in o(L(e)) time. My intuition is based on the difficulty you'd run into when counting L(e1 union e2). I just can't imagine how you'd avoid trying to figure out where L(e1) and L(e2) overlap without enumerating both :/
No comments:
Post a Comment