推广 UNIX 风格正则表达式的泵引理

Question

除了常见的 **、+、?* 运算符之外，大多数 UNIX 正则表达式还具有反斜杠运算符，其中 \1,\2 ,... 匹配最后一个括号中的内容，因此例如 *L=(a*)b\1* 匹配（非常规）语言 *a^nba ^n*。

一方面，这似乎非常强大，因为您可以创建 (a*)b\1b\1 来匹配语言 *a^nba^nba^n*甚至堆栈自动机都无法识别。另一方面，我很确定 *a^nb^n* 不能用这种方式表达。

我有两个问题：

1. 是否有关于该语言系列（UNIX-y 常规）的文献。特别是，是否有针对这些的泵送引理的版本？
2. 有人可以证明或反驳 *a^nb^n* 不能这样表达吗？

Answer 1

您可能正在寻找

• Benjamin Carle 和 Paliath Narendran 的“论扩展正则表达式”LNCS 5457
  • DOI:10.1007/978-3-642-00982-2_24
  • PDF 扩展摘要位于 http:// /hal.archives-ouvertes.fr/docs/00/17/60/43/PDF/notes_on_extended_regexp.pdf
• C. Campeanu、K. Salomaa、S. Yu：实用正则表达式的正式研究， 国际计算机科学基础杂志，卷。 14（2003）1007-1018。
  • DOI:10.1142/S012905410300214X

当然，向前和向后跟踪他们的引用以查找更多关于这个主题的文献。

Answer 2

a^nb^n 是 CFL。语法是

A -> aAb | e

你可以使用 RL 的泵引理来证明 A 不是 RL

Answer 3

Ruby 1.9.1 支持以下正则表达式：

regex = %r{ (?<foo> a\g<foo>a | b\g<foo>b | c) }x

p regex.match("aaacbbb")
# the result is #<MatchData "c" foo:"c">

“Fun with Ruby 1.9 Regular Expressions" 有一个示例，他实际上排列了正则表达式的所有部分，使其看起来像上下文无关语法，如下所示：

sentence = %r{ 
    (?<subject>   cat   | dog   | gerbil    ){0} 
    (?<verb>      eats  | drinks| generates ){0} 
    (?<object>    water | bones | PDFs      ){0} 
    (?<adjective> big   | small | smelly    ){0} 

    (?<opt_adj>   (\g<adjective>\s)?     ){0} 

    The\s\g<opt_adj>\g<subject>\s\g<verb>\s\g<opt_adj>\g<object> 
}x

我认为这意味着至少 Ruby 1.9 .1 的正则表达式引擎（即 Oniguruma 正则表达式引擎）实际上相当于上下文无关语法，尽管捕获组不如实际的解析器生成器那么有用。

这意味着“上下文无关语言的泵引理”应该描述语言类别可由 Ruby 1.9.1 的正则表达式引擎识别。

编辑：哎呀！我搞砸了，没有做重要的测试，这实际上使我上面的答案完全错误。我不会删除答案，因为它仍然是有用的信息。

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x
#I added anchors for the beginning and end of the string
regex.match("aaacbbb")
#returns nil, indicating that no match is possible with recursive capturing groups.

编辑：几个月后回到这里，我发现我在上次编辑中的测试是不正确的。即使 regex 确实像上下文无关语法一样运行，也不应该期望 "aaacbbb" 与 regex 匹配。

正确的测试应该是在像 "aabcbaa" 这样的字符串上，并且它与正则表达式匹配：

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x
regex.match("aaacaaa")
# => #<MatchData "aaacaaa" foo:"aaacaaa">
regex.match("aacaa")
# => #<MatchData "aacaa" foo:"aacaa">
regex.match("aabcbaa")
# => #<MatchData "aabcbaa" foo:"aabcbaa">