Some regexp dialects are actually Turing complete from what I've heard.
EDIT: Yes this seems to be wrong
EDIT: Yes this seems to be wrong
PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.
reference: http://cstheory.stackexchange.com/questions/1047/where-do-mo...