Albeit that argument assumes "classical" regexes. No backrefs like \1 nor any of the 'comfort' in egrep, PCRE, Perl or - even worse - Perl's (?{}), all of which violate Chomsky-3 AFAIR. Then again even Chomsky-3 can be surprising powerful compared to other 'machines' - just limit the others' allowed tape and/or word size... .
(Moritz: small typo: DFA's ch-3, with ch-0 being TM)
Wasn't there some recent discussion or article on Perl6 extensions to regexes (or just on Parsing Expression Grammars/PEG; LUA version maybe?) that contained some comparison to the Chomsky Hierarchy?
