Re^3: check for square-number with a regex

Backreferences are neither enough, nor necessary to make up the difference between languages that are recognized by FAs ("regular expressions") and those that are recognized by PDAs ("context-free grammars").

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ⁿ.

Comment on Re^3: check for square-number with a regex Download Code

Replies are listed 'Best First'.
Re^4: check for square-number with a regex by spx2 (Deacon) on Oct 24, 2009 at 09:56 UTC
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]	[reply] [d/l] [select]
Re^5: check for square-number with a regex by JavaFan (Canon) on Oct 24, 2009 at 11:54 UTC
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".	[reply] [d/l] [select]