Почему рекурсивный regex не regex?
Я прочитывал некоторые ответы в этом вопросе и видел, что несколько человек сказали, что рекурсивные регулярные выражения не были строго говоря регулярными выражениями.
Почему это?
4 ответа
"Строго" регулярные выражения описывают регулярные языки. Но многие особенности, такие как использование обратных ссылок в самом выражении или, например, рекурсия, могут быть использованы для написания регулярных выражений, которые принимают нерегулярные языки.
Например, язык, описанный в
(a+)b+\1
не является регулярным, поскольку вы не можете заставить a появляться одинаковое количество раз до и после bов. По крайней мере, не в обычном языке. С контекстно-свободными или даже контекстно-чувствительными языками дело обстоит совершенно иначе.
Однако регулярные выражения, использующие только элементарные вещи, такие как различные квантификаторы, классы символов и т. д. обычно все же описывают регулярные языки.
Основа других ответов требует понимания теории вычислений. Если вы знакомы с регулярными выражениями только в среде программирования, вы можете не понимать, что регулярные выражения также являются математическими конструкциями. Статья Википедии о регулярных выражениях может дать некоторое представление о теоретических аспектах регулярных выражений.
Строгое определение обычного языка из теоретической информатики может показаться абстрактным с небольшой практической пользой, но если вы когда-либо сталкивались с необходимостью реализации состояния машины для распознавания определенных входных данных, вы можете сэкономить массу бесполезных усилий и лишних хлопот, если заранее докажете, что это невозможно.
Неформальный способ выразить это так: признание обычного языка не может требовать произвольного количества памяти. Лемма о накачке для обычных языков полезна для доказательства того, что конкретный язык ( т.е. , набор строк) не может быть распознан детерминированным конечным автоматом.
Из Введение в формальные языки и автоматы Питера Линца (стр. 115, 3-е изд.):
Теорема 4.8
Пусть L бесконечный регулярный язык. Тогда существует некоторое натуральное число m такое, что любое w ∈ L с | w | ≥ m можно разложить как
w = xyz ,
с
| xy | ≤ м ,
и
| y | ≥ 1,
такое, что
w i = xy i z - Ур. (4.2)
также находится в L для всех i = 0, 1, 2,…
Чтобы распознать бесконечный язык, конечный автомат должен «качать» или повторять некоторая часть его состояний, и это функция y i (обозначение для некоторой строки y , повторенной i раз).
Почти все доказательства, связанные с леммой о накачке, включают доказательство от противного. На странице 117 автор доказывает, что язык L = { a n b n : n ≥ 0} - т.е. , строки вида aaa… bbb… , где подстроки all- a и all- b равны по длине - не являются регулярными:
Предположим, что L регулярно, так что лемма о накачке должна выполняться. Нам неизвестно значение м , но каким бы оно ни было, мы всегда можем выбрать n = m . Следовательно, подстрока y должна полностью состоять из a . Предположим, | y | = к . Тогда строка, полученная с использованием i = 0 в уравнении (4.2), будет
w 0 = a mk b m
и явно не в L . Это противоречит лемме о накачке и тем самым указывает на то, что предположение о регулярности L должно быть ложным.
Другие примеры нерегулярных языков:
- L = { ww R : w ∈ Σ * } - т.е., палиндромы
- L = { w ∈ Σ * : n a ( w ) < n b ( w )} - т.е. ,количество a s меньше, чем количество b s
- L = { a n! : n ≥ 0}
- L = { a n b l : n ≠ l }
- L = { a n b l : n + l - простое число}
Оказывается, то, что мы в общих чертах называем регулярными выражениями, значительно мощнее: сопоставление регулярных выражений с обратными ссылками NP-сложно !
Все регулярные языки могут быть распознаны конечным автоматом. Конечный автомат имеет конечное число состояний и, следовательно, конечную память (отсюда и название). Рекурсивное "регулярное" выражение требует потенциально бесконечного пространства стека для выполнения рекурсии, поэтому его невозможно распознать конечным автоматом, следовательно, оно не является регулярным.