Same question here. I didn't realize that they didn't. regular expression NFA and DFA algorithms are in every compiler book out there. I find it hard to believe that guido et al. didn't know about these algorithms.
Yeah, jimrandomh's comment basically explains it. Perl regexp's have features that can't be implemented by a DFA, like backreferences and arbitrary code evaluation. (I believe you can implement capturing subgroups, you'd just need to annotate the states with a marker for the current position in the string.) Those features are used often enough that you can't just leave them out.
I see no reason why popular languages couldn't implement both algorithms, though, and then select the backtracking one only if the regexp contains backreferences or expressions. It's easy enough to tell if a regexp uses these features, just checking for their existence when the regexp is compiled. Then you could use the fast algorithm when possible and the featureful one when not.
