Perl Monk, Perl Meditation | |
PerlMonks |
Re: Re: Regexp generating strings?by Corion (Patriarch) |
on Aug 18, 2003 at 10:48 UTC ( [id://284539]=note: print w/replies, xml ) | 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.
In Section
Seekers of Perl Wisdom
|
|