3 ms·
> they're at least as powerful as a PDA. PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.
by chimeracoder 13y ago
> they're at least as powerful as a PDA.
PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.
- kazagistar 13y agoI think you are confusing complexity and computability class.