in reply to Is RegEx in Perl not NFA anymore?

The perl regex algorithm/engine is neither DFA nor NFA. The description in Friedl's book is incorrect, and he later have explained that in his website: On the Terms “NFA,” “DFA,” and “Regular Expression”.
In a nutshell, he have used "NFA" to describe regex implementations that have backtracking or backreference, such as /(foo)\1/ matchin "foofoo".

The Perl engine (or almost any other regex implementation out there) cannot be any type of "FA" as it uses backtracking, either recursively or iteratively.

Principle of Least Astonishment: Any language that doesn’t occasionally surprise the novice will pay for it by continually surprising the expert

Replies are listed 'Best First'.
Re^2: Is RegEx in Perl not NFA anymore?
by Laurent_R (Canon) on Oct 20, 2016 at 13:20 UTC
    The perl regex algorithm/engine is neither DFA nor NFA.
    Yeah, Erez, it's good to point this out (++). By strict standards, it is true that the Perl regex engine is neither NFA, nor DFA. In fact, the Perl regex engine is not even doing regular expressions (at least not in the sense of academic regular expressions, as they were defined some 70 years ago). Perl is using highly irregular expressions. And even more so with Perl 6 (which explicitly states it is using the "regex" term, rather than "regular expressions", because it is even further away from the original regular expressions, even if it broadly works according to the same principles).

    Yet, if we are to accept the broader sense of regexes as usually meant nowadays in common programming languages, and more broadly in practical computing, and coming back to the specific question in the original post, I think it can be said that the Perl regex engine is broadly much closer to NFA than to DFA. That's what I meant in my previous post, only that, I did not mean to go in the details of theoretical distinctions which are probably very important for research but of relatively little significance for practical computing.

[reply]
Re^2: Is RegEx in Perl not NFA anymore?
by Your Mother (Archbishop) on Oct 20, 2016 at 11:27 UTC

    This is the description from his book so I would say he clarified the issue, not corrected–

    The true mathematical and computational meaning of “NFA” is different from what is commonly called an “NFA regex engine.” In theory, NFA and DFA engines should match exactly the same text and have exactly the same features. In practice, the desire for richer, more expressive regular expressions has caused their semantics to diverge.
[reply]

In Section Seekers of Perl Wisdom