Perl&#x27;s algorithm has more power than an NFA, therefore, it is not an NFA. It&#x27;s as simple as that. That certain inputs happen to correspond to a configuration solvable by an NFA does not make it an NFA. The worst part about calling it an NFA is that it misleads everyone about the theory and suggests that the engine is less powerful than it really is.<p>I completely understand why it looks like an NFA.<p>&gt; What the heck do you call it?<p>Anything but an NFA? My personal preference is unbounded backtracking (still not <i>quite</i> right), or just &quot;Perl regexes.&quot;<p>&gt; (As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.)<p>I read that book when I was a young pup and remained hopelessly uninformed about the entire situation until my first complexity theory class during my undergraduate study almost ten years ago.<p>That book is fantastic if you care about optimizing Perl regexes. It otherwise does a great disservice to theory and has likely been the cause of uncountable confusion. When pointed out the inaccuracy, Friedl essentially had the same response as you. It&#x27;s tragic, frankly.<p>PCRE&#x27;s documentation even cites Friedl&#x27;s book when describing their implementation by calling it the &quot;NFA algorithm.&quot; PCRE also has a supposed &quot;DFA,&quot; but its description makes it sound more like the <i>actual</i> NFA algorithm (since it maintains multiple states simultaneously).