Regular expression: language generator

Question

Given a regular expression in C#, is there a way to generate a word that is accepted by this regular expression?

For instance, let's consider:

[ab]c*b*

Is there a function that can automatically generate a enumeration like:

a
b
ac
ab
bc
bb
acb
bcb
acc
bcc
...

Obviously this list being infinite of potentially of as-long-as-you-want words, the generator would have to be smart in order to output things from the simplest to the most complex, without being trapped in infinite loops.

I think this would be a useful tool in order to validate regular expression. In general it's easy to see that a regular expression accepts words that you planned it would accept. It's usually much more difficult to see what other words it would accept.

EDIT: This question is not about how to do it, but rather: is there anything out there that I could use to do it in C#?

Answer 1

This isn't even a C#-specific question; I think you can do this with any true regex.

It seems to me like you should be able to tell a generation story for any regex match that's just a list of rewrites. In your example [ab]c*b* can generate acccbbb; that's [ab]c*b*->ac*b*->acccb*->acccbbb. For each operator we can imagine enumerating all the ways it rewrites; then it's just a question of enumerating all combinations of rewrites, which boils down to enumerating all the N-tuples of naturals.

edit: N-tuples of naturals is a glib comparison. But you could imagine essentially performing a breadth-first traversal over rewrite states, outputting each string that all operators have been rewritten out of.