Well said. I will include this in the article. Couldn't figure out how to say it well before because they are still not equivalent to context-free languages, th

Well said. I will include this in the article. Couldn't figure out how to say it well before because they are still not equivalent to context-free languages, they are just sometimes powerful enough to describe some of the context-free languages. Therefore I didn't include it. I think only the regex implementations with recursion are context-free. Others are not, therefore I wouldn't say "most" of them are. You're right that I was surprised because I hadn't heard of recursive regular expressions in Perl before. Update: I just remembered that extended regular expressions can even recognize recursive languages. Here is a regex that decides if the number is a prime: perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ is prime"' This goes beyond context-free, therefore I couldn't just say "context-free" carelessly in the article.