Poor man's answer:

it is possible indeed, and the demonstration is quite simple:

1. Given the maximum length of the string, generate every possible string and match against the regexp. It's obviously a finite number, possibly huge but finite.
2. If the string matches, push it into an array which is initially empty. A number less than a finite number (or equal) is certainly finite.

Now this is purely theoretical and ridiculously inefficient, but it can be done quite easily as a proof of concept if you like.

Be careful when you generate the possible strings (if you're really going to), Unicode is out there!

Another much more reasonable approach would be studying the Perl code that generates the Finite State Machine used to match a certain regexp and use that as a starting point for generating strings instead of matching them. It wouldn't probably be too bad if backtracking and other fancy features weren't there.

-- TMTOWTDI