&gt; Reducing a parser to a DFA (deterministic finite automaton) provides it with measurable performance per character parsed. If an NFA (non-deterministic finite automaton) is used instead, then an attacker can abuse backtracking to increase parse time, often exponentially.<p>An NFA does <i>not</i> use backtracking - at least in a sensible implementation. The problem is that most implementors of RE engines prefer &quot;obvious hands-on&quot; implementation that uses backtracking instead of understating the elegant theory behind NFAs. Here is how to implement an NFA without using backtracking:<p>&gt; <a href="https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp1.html" rel="nofollow">https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp1.html</a><p>Addendum: And it is also a bad idea to convert am NFA to an DFA for parsing because the number of necessary states can explode exponentially by this transformation.