Classic regular expressions are level 3 in the Chomsky classification, but most regex implementations have features that aren't a part of "regular languages".

The upside is that they are more expressive, but the downside is that it's no longer O(n) to parse a string.

Worst case for some regexes can be exponential, never run untrusted regexes on your server unless you use a safe implementation like re2 which was developed for Google Code Search.