alt Hacker NewsThey are controversial because supporting them raises matching time to O(2^n) in the worst case - which is dangerous - while not supporting them enables matching time to be O(n) in the worst case. And a user might not be aware of that danger.
Also, I think it's misleading to mention NFAs and DFAs alone, like there's no deeper reason. The deeper reason is that:
Regexes (or NFAs, or DFAs) classify exactly the properties of strings which can be checked in constant space.
Briefly returning to backreferences, supporting them makes constant space unachievable. They also make linear time unachievable, since matching them becomes NP-COMPLETE.
Also, no regex implementation actually uses DFAs. NFAs yes, but DFAs no. The point of NFAs is that they're easy to execute in constant space and linear time, while also making concatenation and Kleene star easy to implement. It seems much harder to implement concatenation and Kleene star using most other constant-space automata - like DFAs - which is what actually forced people to invent NFAs.
I think we are actually on the same page, but it is funny that we express things in exactly the opposite way as well as reach opposite conclusions. :)
It's not about being pedantic, quite the opposite It's intuitive to use circles and arrows as the mental model, instead of the cryptic regex syntax. Both have the same semantics. The quite visual representaton of the finite automata makes the meaning more approachable, not unlike the marble run illustration.
In contrast, bringing "constant space" and "O(n) matching" and NP-completeness etc into the discussion is all formally correct (and I'm a big fan of formally correct) but that's where things become pedantic from the common folk's POV and is also where you lose people who just want to understand how something works practically.
Therefore I'm saying, start withthe easy circles-and-arrows intuition and only go to the theoretical background (aka be pedantic) once people want to know more.
(Backrefs can't be expressed with circles-and-arrows which illustrates why they are something special.)