As I pointed out, a classical context-free language that isn't a regular expression is aⁿbⁿ. You cannot match that with 5.8 regular expressions (assuming no jumping back to the interpreter using (?{}) or (??{})), proving that backreferences aren't enough. But in 5.10, you can write /^(a(?1)b)$/, which doesn't use backreferences. It does use recursion, but recursion is the difference between an FA and a PDA.

Now, I think that due to backreferences, Perl regular expressions are more powerful than context-free grammars, but I cannot think of a language that is matched by a Perl regular expression, and not by a context-free grammar. And I don't think Perl regular expressions are as powerful as context sensitive grammars (which requires a TM). For instance, I don't think there's a Perl regular expression to match aⁿbⁿcⁿ.

I think you're aware of this solution for aⁿbⁿcⁿ but I'll post it anyway(it uses ??{} blocks and ?{} and is a Perl regex).

$r = qr/^(a+b)(?{ $a = -1+length $^N; })(??{ $b=$a-1;"(b{$b})" })(??{ 
+"(c{$a})" })/x;

sub test {
        print
        $_[0] =~ $r
        ? "matched\n"
        : "not matched\n";
}

test "aaabbbccc";
test "aaaabbbccc";
test "aaaabbbbccc";
test "aaaabbbbcccc";
test "aabbbbcccc";
test "abc";
test "aabbcc";
[download]

Result on Perl v5.8.8:

matched
not matched
not matched
matched
not matched
matched
matched
[download]

I (and others in this thread) explicitely mentioned no using (?{}) and (??{}). Allowing those means you have the full power of Perl available. It would mean that anything you can do in Perl, you can to with a "regular expression", and the question "can I do foo with a regular expression" becomes a non-question.

And I would have used (?{}) differently anyway. Something like:

/^(a+)(b+)(c+)$(?(?{length($1) == length($2) && length($2) == length($
+3)})|(*FAIL))/;
[download]

But that's just a fancy way of writing:

/^(a+)(b+)(c+)$/ && length($1) == length($2) && length($2) == length($
+3);
[download]

And you can solve the "match a square" with:

/^([0-9]+)$(?(?{sqrt($1) == int sqrt($1)})|(*FAIL))/;
[download]

Or in general, match "whatever" by:

/^(.*)$(?(?{is_whatever($1)})|(*FAIL))/;
[download]

after writing the appropriate "is_whatever" function.

But that means the question no longer is "how can I do foo with a regexp", but "how can I do foo in Perl".