6

ほとんどの UNIX 正規表現には、通常の**, +,?*演算子の他に、最後の括弧内のものと一致するバックスラッシュ演算子がある\1,\2,...ため、たとえば*L=(a*)b\1*(非正規の) language と一致します*a^n b a^n*。

一方で、スタックオートマトンでも認識できない(a*)b\1b\1言語に合わせて作成できるため、これはかなり強力に思えます。*a^n b a^n b a^n*一方で、*a^n b^n*このように表現することはできないと確信しています。

2 つの質問があります。

  1. この言語ファミリーに関する文献はありますか (UNIX-y レギュラー)。特に、これらのポンピング補題のバージョンはありますか?
  2. *a^n b^n*このように表現できないことを誰かが証明または反証できますか?
4

3 に答える 3

2

あなたはおそらく探している

もちろん、彼らの引用を前後にたどって、この主題に関する他の文献を見つけてください。

于 2010-04-18T05:01:34.803 に答える
0

a^nb^n は CFL です。文法は

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 の正規表現エンジン (鬼車の正規表現エンジン) が実際には文脈自由文法と同等であることを意味していると思いますが、キャプチャー グループは実際のパーサー ジェネレーターほど有用ではありません。

これは、「文脈自由言語のポンピング補題」は、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.

EDIT：何ヶ月も後にこれに戻ってきて、最後の編集での私のテストが間違っていたことを発見しました. 文脈自由文法のように動作する場合でも、"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 に答える