Вопрос #1615371

Критерии (когда расширение регулярных выражений остаётся или выходит за рамки регулярных языков):
- Остаётся регулярным, если используются только операции, эквивалентные регулярным операциям (объединение, конкатенация, звезда Клини), фиксированные повторения (\{n\}), символьные классы, группировки без сравнения прошлых захватов, и любые конструкции, которые можно реализовать конечным автоматом. Фиксированный по длине lookbehind/ lookahead тоже не увеличивает мощность (эквивалентно конечному числу состояний).
- Выходит за рамки регулярных языков, если есть механизмы, требующие сравнения или связывания подстрок произвольной (непредварительно ограниченной) длины или неограниченного счёта/рекурсии: в частности, обратные ссылки (backreferences) на захваченные подстроки произвольной длины, рекурсивные вызовы (например, PCRE (?R)), балансирующие группы и некоторые условные конструкции. Эти механизмы дают возможность выражать языки, требующие неограниченной памяти (контекстно-свободные или более сильные).
Пример паттерна/языка, который невозможно распознать конечным автоматом:
- Паттерн (в regex-движках с backreferences): ^(.+)\1$ — он описывает язык
\(L = \{\, ww \mid w \in \Sigma^+ \,\}\) (двойное повторение некоторой непустой строки).
Почему конечный автомат не может распознать \(L\) (доказательство через лемму о накачке):
1) Предположим, что \(L\) регулярный. Тогда существует константа (длина накачки) \(p\).
2) Рассмотрим строку \(s = a^p b a^p b\). Это строка вида \(ww\) с \(w = a^p b\), значит \(s \in L\) и \(|s| \ge p\).
3) По лемме о накачке существует разложение \(s = xyz\) такое, что \(|xy| \le p\) и \(|y| > 0\). Поскольку \(|xy| \le p\), подстрока \(y\) состоит только из символа \(a\) в первой группе \(a^p\).
4) Возьмём «выпомпленную» строку \(s' = xz\) (то есть выкинем хотя бы один символ из \(y\)). Тогда в первой половине строки стало меньше символов \(a\), чем во второй половине, и \(s'\) не имеет вида \(ww\), значит \(s' \notin L\).
5) Это противоречит свойству леммы о накачке (для регулярного языка все такие \(s'\) должны оставаться в языке). Значит исходное предположение неверно: \(L\) не регулярный.
Интуитивно: распознавать \(L\) требуется сравнивать две половины произвольной длины на точное совпадение — это требует неограниченной памяти (неподвластно конечному автомату). Backreferences реализует именно такую проверку равенства подстрок, поэтому добавление их к regex-движку позволяет описывать нерегулярные языки.