Re: Re: Regexp generating strings?by Corion (Pope)
|on Aug 18, 2003 at 10:48 UTC||Need Help??|
Warning: Theoretical but impractical stuff follows: I think for plain regular expressions (not the Perl stuff), it is possible to check whether a RE matches any string, and in the process of doing that, you (can) come across a lot of matching strings :
If all of the above are true (and I remember them being true), then you "only" have to enumerate all strings from the alphabet from length 0 to the number of states of the DFA representing your RE. After that, you can go up to 2* number of states of DFA, to see whether it has loops.
The number of states in a DFA does not directly relate to the number of characters in your RE, if I remember correctly, it can be up to 2^n with n the number of characters from your alphabet in your RE (that's a rough number, as I equate the NFA with the RE here).
This means that, for nontrivial REs, you will have a large space of strings to search. It might be easier to randomly generate strings and check whether they match, maybe guided by some heuristics, like alphabetical chars within the RE.