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 :
- Any regular expression can be written as a finite deterministic automaton.
- Every deterministic finite automaton (DFA) either accepts no word at all or at least one word that is equal or less the number of states it has.This theorem has some name I forgot...
- If a DFA accepts a word of a length greater than the number of states, it has a loop.
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.
perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ; # The
$d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider
($c = $d->accept())->get_request(); $c->send_response( new #in the
HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' # web
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
Outside of code tags, you may need to use entities for some characters:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||