6

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

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

我有两个问题：

  1. 有没有关于这个语言家族的文献（UNIX-y 常规）。特别是，这些引理是否有一个版本？
  2. 有人可以证明或反驳*a^n b^n*不能以这种方式表达的事情吗？
4

3 回答 3

2

您可能正在寻找

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

于 2010-04-18T05:01:34.803 回答
0

a^nb^n 是节能灯。语法是

A -> aAb | e

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

于 2010-04-13T02:33:48.777 回答
-1

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.

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

正确的测试应该在一个类似的字符串上"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">
于 2010-04-18T04:51:45.723 回答