My response was triggered by wolfge saying, &quot;...implementors of RE engines...&quot; and attributing using backtracking to laziness.<p>However the most widely used RE engines in the wild use backtracking because that is the easiest way to handle the full feature set that is asked of them.  That&#x27;s not to say that they couldn&#x27;t be implemented in a way that was able to handle strict regular expressions without backtracking, while backtracking only when they need to.  (Perl makes a modest attempt in that direction, but doesn&#x27;t do it completely.)<p>And then when programmers ask how the engine works, they start with the simple version for simple features.  The naive explanation is of an actual NFA.  And then someone goes off and implements one for a project, and they just follow that.  Now you have an engine which is an honest NFA, and uses backtracking.  It doesn&#x27;t need to because it doesn&#x27;t support extra features, but it is simple, it works, and if you ever needed to extend it, it is obvious how you&#x27;d go about it.<p>So there are two reasons other than laziness to implement an RE engine with backtracking.  The first is that your RE engine supports (or might in the future) features that require it.  The second is that it is easier to find and follow explanations of backtracking.<p><i>This is exactly the problem. It is wrong to say that Perl uses an NFA algorithm. It literally cannot be true because Perl implements features that are NP-complete.</i><p>Not true!<p>If you hand Perl&#x27;s RE engine a regular expression that is actually regular, then Perl will construct a set of states that are a recognizable NFA, and then will attempt to match the NFA to the string using the obvious backtracking algorithm.  Admittedly the states are decorated with fields which COULD specify non-NFA stuff.  The code it passes through will have checks for whether to trigger features that an NFA can&#x27;t do.  But what it actually will do is construct a recognizable NFA, and attempt to match it to the string.<p>Now throw a non-regular &quot;regular expression&quot; at the same thing and you&#x27;ll construct a data structure that clearly isn&#x27;t a proper NFA.  What the heck do you call it?  It is some type of extended state machine, but it is easiest to think of it as &quot;NFA with some extra stuff&quot;.  And that is exactly how the people who <i>do</i> work on that code think of it.  With no alternate terminology and thinking of it as an NFA, is there any wonder that they describe it as an NFA?<p>(As well, that is how it was described in a number of popular and widely read books.  For example pick up _Mastering Regular Expressions_.)