perlfaq nodetype
faq_monk
<P>
While it's true that Perl's regular expressions resemble the DFAs (deterministic finite automata) of the
<CODE>egrep(1)</CODE> program, they are in fact implemented as NFAs (non-deterministic finite automata) to allow backtracking and backreferencing. And they aren't POSIX-style either, because those guarantee worst-case behavior for all cases. (It seems that some people prefer guarantees of consistency, even when what's guaranteed is slowness.) See the book ``Mastering Regular Expressions'' (from O'Reilly) by Jeffrey Friedl for all the details you could ever hope to know on these matters (a full citation appears in
[perlman:perlfaq2|the perlfaq2 manpage]).
<P>