обобщение насосной леммы для регулярных выражений стиля UNIX
Большинство регулярных выражений 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* не может быть выражен этот путь.
У меня есть два вопроса:
- Есть ли любая литература по этой языковой семье (постоянный UNIX-y). В частности, есть ли версия насосной леммы для них?
- Может кто-то доказывать или опровергать, это
*a^n b^n*не может быть выражен этот путь?
3 ответа
a ^ n b ^ n - это КЛЛ. Грамматика такова
A -> aAb | e
, вы можете использовать лемму о накачке для RL, чтобы доказать, что A не является RL
Вы, вероятно, ищете
- Бенджамин Карл и Палиат Нарендран «О расширенных регулярных выражениях» 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.
и, конечно, следите за их цитатами вперед и назад, чтобы найти дополнительную литературу по этой теме.
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" не должно соответствовать регулярному выражению , даже если регулярное выражение действительно работает как контекстно-свободная грамматика.
Правильный тест должен быть в строке типа «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">