4 ms·
Perl's regex engine must use something stronger than plain NFAs. The expressive power of NFAs and DFAs is exactly the same. They both recognize the regular lang
by more_original 11y ago
Perl's regex engine must use something stronger than plain NFAs. The expressive power of NFAs and DFAs is exactly the same. They both recognize the regular languages, which is less than what can be expressed with Perl "regular expressions".
- brudgers 11y agoI'm using Friedl's classification scheme for regex engines from Mastering Regular Expressions. I don't know of a more standard survey regarding regex's as implemented in various programming languages. Anyway, from a practical standpoint an NFA has to be implemented as a push down automata in the Von Neumann machines we currently have to allow backtracking to simulate simultaneous exploration of the arbitrary number of DFA states that a single NFA state may represent. That doesn't make Friedl's classification useless.