Unfortunately what we nowadays call "regular expressions" aren't the regular expressions from math class -- they can match against much more than regular languages. I believe PCRE, i.e., the "regular expression" language for most regex libraries, is Turing-complete though I can't find a citation for that right now.