For a discussion of the "DFA" engines, I'd recommend Russ Cox's article series. The NFA implementations you speak of have problems because they use backtrackin

For a discussion of the "DFA" engines, I'd recommend Russ Cox's article series. The NFA implementations you speak of have problems because they use backtracking and take worst case exponential time. Most implementations are in fact not NFAs, since for example, an NFA is not a powerful enough tool to resolve backreferences (which are NP-complete). Both NFAs and DFAs in fact have equivalent computational power, and either can be used to perform regular expression matching in linear time. There are of course lots of performance differences in practice. Friedl's book is great for what it is: a guide to optimizing regexes that search via backtracking.