Comment by nabla9

The problem is not DFA vs NFA.

“regular expression” has different meaning in programming context and formal language context. Regular expressions in regex libraries do more than match regular languages.

PCRE can recognize also all context free languages and some subset of context-sensitive languages. Just having backreferences makes the problem NP-hard.