обобщение леммы прокачки для регулярных выражений в стиле UNIX

Question

Большинство регулярных выражений 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-й регулярный). В частности, существует ли версия леммы прокачки для них?
2. Может ли кто-то доказать или опровергнуть, что *a^n b^n* не может быть выражен таким образом?

Answer 1

Вы, наверное, ищете

• Бенджамин Карл и Палиат Нарендран "О расширенных регулярных выражениях" 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. Кампеану, К. Саломаа, С. Ю.: Формальное исследование практических регулярных выражений, Международный журнал основ информатики , Vol. 14 (2003) 1007 - 1018.
  • DOI: 10,1142 / S012905410300214X

и, конечно, следуйте их цитатам вперед и назад, чтобы найти больше литературы на эту тему.

Answer 2

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">

" Удовольствие от регулярных выражений Ruby 1.9 " есть пример, в котором он фактически упорядочивает все части регулярного выражения так, чтобы это выглядело как контекстная грамматика следующим образом:

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" не должно совпадать с regex, даже если 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">

Answer 3

a ^ n b ^ n - КЛЛ. Грамматика

A -> aAb | e

Вы можете использовать лемму прокачки для RL, чтобы доказать, что A не является RL