Влияет ли lookaround на то, какие языки могут сопоставляться регулярными выражениями?

Question

В современных движках регулярных выражений есть некоторые функции, которые позволяют вам сопоставлять языки, которые не могут быть сопоставлены без этой функции. Например, следующее регулярное выражение с использованием обратных ссылок соответствует языку всех строк, состоящих из повторяющегося слова: (.+)\1. Этот язык не является регулярным и не может быть сопоставлен с регулярным выражением, которое не использует обратных ссылок.

Влияет ли lookaround и на какие языки можно сопоставить регулярное выражение? То есть Есть ли языки, которые могут быть сопоставлены с использованием lookaround, которые не могут быть сопоставлены в противном случае? Если да, то верно ли это для всех разновидностей внешнего вида (негативного или позитивного прогнозирования или прогнозирования) или только для некоторых из них?

Answer 1

Ответ на заданный вами вопрос о том, можно ли распознать больший класс языков, чем обычные языки с помощью регулярных выражений, дополненных lookaround, - нет.

Доказательство относительно простое, но алгоритм преобразования регулярного выражения, содержащего обходные пути, в одно без, грязный.

Во-первых: обратите внимание, что вы всегда можете отрицать регулярное выражение (над конечным алфавитом). Учитывая автомат конечного состояния, который распознает язык, сгенерированный выражением, вы можете просто обменять все принимающие состояния на неприемлемые состояния, чтобы получить FSA, который точно распознает отрицание этого языка, для которого существует семейство эквивалентных регулярных выражений ,

Второе: поскольку регулярные языки (и, следовательно, регулярные выражения) закрыты при отрицании, они также закрыты при пересечении, поскольку A пересекается с B = neg (neg (A) union neg (B)) по законам де Моргана. Другими словами, учитывая два регулярных выражения, вы можете найти другое регулярное выражение, которое соответствует обоим.

Это позволяет вам моделировать выражения поиска. Например, u (? = V) w соответствует только выражениям, которые будут соответствовать uv и uw.

Для негативного взгляда вам понадобится регулярное выражение, эквивалентное теореме множеств A \ B, которая является просто A-пересечением (neg B) или эквивалентно neg (neg (A) union B). Таким образом, для любых регулярных выражений r и s вы можете найти регулярное выражение r-s, которое соответствует тем выражениям, которые соответствуют r и не соответствуют s. В отрицательных терминах: u (?! V) w соответствует только тем выражениям, которые соответствуют uw - uv.

Есть две причины, по которым полезно использовать lookaround.

Во-первых, потому что отрицание регулярного выражения может привести к чему-то гораздо менее аккуратному. Например q(?!u)=q($|[^u]).

Во-вторых, регулярные выражения делают больше, чем выражения соответствия, они также потребляют символы из строки - или, по крайней мере, так мы думаем о них. Например, в python я забочусь о .start () и .end (), таким образом, конечно:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

В-третьих, и я думаю, что это довольно важная причина, отрицание регулярных выражений не слишком хорошо подходит для конкатенации. neg (a) neg (b) - это не то же самое, что neg (ab), что означает, что вы не можете перевести взгляд из контекста, в котором вы его нашли, - вам нужно обработать всю строку. Я полагаю, что это неприятно для людей работать и нарушает интуицию людей относительно регулярных выражений.

Надеюсь, я ответил на ваш теоретический вопрос (поздно ночью, так что извините, если мне неясно). Я согласен с комментатором, который сказал, что это имеет практическое применение. Я столкнулся с той же проблемой, когда пытался почистить некоторые очень сложные веб-страницы.

EDIT

Приношу свои извинения за неясность: я не верю, что вы можете дать доказательство регулярности регулярных выражений + обходных путей структурной индукцией, мой пример u (?! V) w должен был быть именно этим, примером и легкий в этом. Причина, по которой структурная индукция не сработает, заключается в том, что обходные пути ведут себя несоставным образом - то, о чем я пытался рассказать об отрицаниях выше. Я подозреваю, что у любого прямого формального доказательства будет много грязных деталей. Я пытался придумать простой способ показать это, но не могу придумать один из них на макушке.

Чтобы проиллюстрировать использование первого примера Джоша ^([^a]|(?=..b))*$, это эквивалентно DFSA из 7 состояний со всеми принимающими состояниями:

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

Регулярное выражение для одного состояния A выглядит следующим образом:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

Другими словами, любое регулярное выражение, которое вы получите, исключив обходные пути, в общем случае будет намного длиннее и сложнее.

Чтобы ответить на комментарий Джоша - да, я думаю, что самый прямой способ доказать эквивалентность - через FSA. Что делает этот беспорядок так это то, что обычный способ построения FSA - это недетерминированная машина - гораздо проще выразить u | v как простую машину, построенную из машин для u и v с эпсилон-переходом к двум из них. Конечно, это эквивалентно детерминированной машине, но с риском экспоненциального взрыва состояний. Принимая во внимание, что отрицание намного легче сделать с помощью детерминированной машины.

Общее доказательство будет заключаться в том, чтобы взять декартово произведение двух машин и выбрать те состояния, которые вы хотите сохранить в каждой точке, в которую вы хотите вставить обходной путь. Приведенный выше пример иллюстрирует, что я имею в виду в некоторой степени.

Приношу свои извинения за то, что не предоставил строительство.

ДОПОЛНИТЕЛЬНОЕ РЕДАКТИРОВАНИЕ: Я нашел в блоге сообщение , в котором описан алгоритм генерации DFA из регулярного выражения, дополненного поисковыми запросами. Это хорошо, потому что автор расширяет идею NFA-e с «мечеными эпсилон-переходами» очевидным образом, а затем объясняет, как преобразовать такой автомат в DFA.

Я думал, что что-то подобное будет способом сделать это, но я рад, что кто-то написал это. Это было вне меня, чтобы придумать что-то такое аккуратное.

Answer 2

Как утверждают другие ответы, обходные пути не добавляют дополнительной мощности к регулярным выражениям.

Я думаю, что мы можем показать это, используя следующее:

Одна галька 2-NFA (см. Раздел «Введение» к этой статье).

1-каменная 2NFA не имеет отношения к вложенным запросам, но мы можем использовать вариант мульти-каменной 2NFA (см. Раздел ниже).

Введение

2-NFA - это недетерминированный конечный автомат, который может перемещаться влево или вправо на своем входе.

В машине с одной галькой машина может поместить гальку на входную ленту (т. Е. Пометить определенный входной символ галькой) и, возможно, выполнять различные переходы в зависимости от того, есть галька в текущей позиции ввода или нет.

Известно, что One Pebble 2-NFA имеет такую ​​же мощность, что и обычный DFA.

Не вложенные Lookaheads

Основная идея заключается в следующем:

2NFA позволяет нам возвращаться назад (или «передняя дорожка»), перемещаясь вперед или назад по входной ленте. Таким образом, для lookahead мы можем выполнить сопоставление для регулярного выражения lookahead, а затем вернуть обратно то, что мы использовали, в соответствии с выражением lookahead. Чтобы точно знать, когда прекратить возвращаться, мы используем гальку! Мы опускаем гальку, прежде чем войти в dfa, чтобы наблюдатель отметил место, где должен прекратиться возвратный ход.

Таким образом, в конце работы с нашей строкой через гальку 2NFA мы знаем, соответствовали ли мы выражению предпросмотра или нет, а оставленный ввод (т. Е. То, что осталось использовать) - это именно то, что требуется для соответствия оставшимся. 1029 *

Итак, заглянем в форму u (? = V) w

У нас есть DFA для u, v и w.

Из принимающего состояния (да, мы можем предположить, что есть только один) DFA для вас, мы делаем электронный переход в начальное состояние v, помечая входные данные галькой.

Из принимающего состояния для v мы осуществляем электронный переход в состояние, которое продолжает перемещать вход влево, пока не найдет гальку, а затем перейдет в начальное состояние w.

Из отклоняющего состояния v мы осуществляем электронный переход в состояние, которое продолжает двигаться влево до тех пор, пока не найдет гальку, и перейдет в принимающее состояние u (то есть, где мы остановились).

Доказательство, используемое для обычных NFA, чтобы показать r1 | r2, или r * и т. д., переносят для этой одной гальки 2nfas. См. http://www.coli.uni -saarland.de / projects / milca / courses / coal / html / node41.html # регулярноlanguages.sec.regexptofsa для получения дополнительной информации о том, как составные машины собираются вместе, чтобы дать большую машину для выражения r * и т. д.

Причина, по которой вышеприведенные доказательства для r * и т. Д. Работают, заключается в том, что обратное отслеживание гарантирует, что входной указатель всегда находится в правильном месте, когда мы вводим компонент nfas для повторения. Кроме того, если используется галька, то она обрабатывается одним из компьютеров с компонентами предварительного просмотра. Поскольку нет переходов от прогнозирующей машины к прогнозирующей машине без полного возврата и возврата гальки, все, что нужно - это машина с одной галькой.

Например, рассмотрим ([^ a] | a (? = ... b)) *

и строка abbb.

У нас есть abbb, который проходит через peb2nfa для a (? = ... b), в конце которого мы находимся в состоянии: (bbb, matched) (т. Е. На входе bbb остается, и он соответствует «а» с последующим «..б»). Теперь из-за * мы возвращаемся к началу (см. Конструкцию в ссылке выше) и вводим dfa для [^ a]. Совпадение b, вернитесь к началу, введите [^ a] снова два раза и затем подтвердите.

Работа с вложенными Lookaheads

Для обработки вложенных просмотров мы можем использовать ограниченную версию k-pebble 2NFA, как определено здесь: Результаты сложности для автоматов с двусторонним и многокаменным движением и их логики (см. Определение 4.1 и теорему 4.2) .

Как правило, 2-каменные автоматы могут принимать нерегулярные множества, но со следующими ограничениями можно показать, что автоматы k-камешков являются регулярными (теорема 4.2 в статье выше).

Если галькой являются P_1, P_2, ..., P_K

• P_ {i + 1} не может быть размещен, если P_i уже на ленте, а P_ {i} не может быть поднят, если P_ {i + 1} не на ленте. По сути, гальку нужно использовать в режиме LIFO.

• Между временем P_ {i + 1} и временем, когда P_ {i} выбран или P_ {i + 2}, автомат может пройти только подслово, расположенное между текущим расположение P_ {i} и конец входного слова, который лежит в направлении P_ {i + 1}. Более того, в этом подслове автомат может действовать только как 1-галечный автомат с Pebble P_ {i + 1}. В частности, нельзя поднимать, помещать или даже ощущать присутствие другой гальки.

Так что, если v является вложенным выражением предпросмотра глубины k, то (? = V) является вложенным выражением предпросмотра глубиной k + 1. Когда мы заходим в машину, ведущую в сторону, мы точно знаем, сколько камушков должно быть размещено до сих пор, и поэтому можем точно определить, какую гальку нужно разместить, и когда мы выходим из этой машины, мы знаем, какую гальку поднять. Все машины на глубине t вводятся путем помещения гальки t и выходятся (то есть мы возвращаемся к обработке машины глубины t-1), удаляя гальку t. Любой запуск всей машины выглядит как рекурсивный вызов дерева dfs, и к двум вышеуказанным ограничениям машины с несколькими камушками можно отнести.

Теперь, когда вы объединяете выражения для rr1, так как вы конкатируете, числа гальки r1 должны увеличиваться на глубину r. Для r * и r | r1 нумерация гальки остается неизменной.

Таким образом, любое выражение с заглядыванием может быть преобразовано в эквивалентную машину с несколькими камешками с указанными выше ограничениями в размещении камешков и поэтому является регулярным.

Заключение

Это в основном устраняет недостаток в оригинальном доказательстве Фрэнсиса: способность не допускать, чтобы выражения прогнозных данных потребляли все, что требуется для будущих совпадений.

Так как Lookbehinds - это просто конечная строка (на самом деле не регулярные выражения), мы можем сначала иметь с ними дело, а затем иметь дело с lookahead.

Извините за неполную рецензию, но полное доказательство будет включать в себя много рисунков.

Мне это кажется правильным, но я буду рад узнать о любых ошибках (которые мне, похоже, нравятся: -)).

Answer 3

Я согласен с другими постами, что поиск обходится регулярно (имеется в виду, что он не добавляет фундаментальных возможностей регулярным выражениям), но у меня есть аргумент для него, который является более простым IMO, чем другие, которые я видел.

Я покажу, что обходной путь является регулярным, предоставляя конструкцию DFA. Язык является регулярным, если и только если у него есть DFA, который его распознает. Обратите внимание, что Perl на самом деле не использует DFA для внутренних целей (подробности см. В этом документе: http://swtch.com/~rsc/regexp/regexp1.html), но мы создаем DFA для целей доказательства.

Традиционным способом построения DFA для регулярного выражения является сначала создание NFA с использованием алгоритма Томпсона. Учитывая два фрагмента регулярных выражений r1 и r2, алгоритм Томпсона предоставляет конструкции для конкатенации (r1r2), чередования (r1|r2) и повторения (r1*) регулярных выражений. Это позволяет вам строить NFA по крупицам, который распознает исходное регулярное выражение. Для получения более подробной информации см. Выше.

Чтобы показать, что положительный и отрицательный взгляды являются регулярными, я приведу конструкцию для конкатенации регулярного выражения u с положительным или отрицательным прогнозом: (?=v) или (?!v). Только сцепление требует особого отношения; обычные конструкции чередования и повторения работают нормально.

Конструкция для u (? = V) и u (?! V):

Другими словами, подключите каждое окончательное состояние существующего NFA для u к обоим состояниям принятия и к NFA для v, но измените его следующим образом. Функция f(v) определяется как:

• Пусть aa(v) будет функцией NFA v, которая меняет каждое принимаемое состояние на «антипринятое состояние». Состояние анти-принятия определяется как состояние, которое вызывает сбой сопоставления, если любой путь через NFA заканчивается в этом состоянии для данной строки s, даже если другой путь через v для s заканчивается в состоянии принятия.
• Пусть loop(v) будет функцией в NFA v, которая добавляет самопереход в любое состояние принятия. Другими словами, как только путь приводит к состоянию принятия, этот путь может оставаться в состоянии принятия всегда, независимо от того, какой ввод следует.
• Для негативного взгляда, f(v) = aa(loop(v)).
• Для позитивного взгляда, f(v) = aa(neg(v)).

Чтобы дать интуитивно понятный пример того, почему это работает, я буду использовать регулярное выражение (b|a(?:.b))+, которое является несколько упрощенной версией регулярного выражения, которое я предложил в комментариях к доказательству Фрэнсиса. Если мы используем мою конструкцию вместе с традиционными конструкциями Томпсона, мы получим:

e s - это эпсилон-переходы (переходы, которые могут быть приняты без использования какого-либо ввода), а состояния антиприятия помечены X. В левой половине графика вы видите представление (a|b)+: любой a или b переводит график в состояние принятия, но также разрешает переход обратно в начальное состояние, чтобы мы могли сделать это снова. Но учтите, что каждый раз, когда мы сопоставляем a, мы также вводим правую половину графика, где мы находимся в состоянии антиприятия, пока не сопоставим «любой», за которым следует b.

Это не традиционный NFA, потому что традиционные NFA не имеют антиприемлемых состояний. Однако мы можем использовать традиционный алгоритм NFA-> DFA, чтобы преобразовать его в традиционный DFA. Алгоритм работает как обычно, где мы моделируем несколько прогонов NFA, делая наши состояния DFA соответствующими подмножествам состояний NFA, в которых мы могли бы быть. Единственный поворот заключается в том, что мы немного расширяем правило для принятия решения, является ли состояние DFA принять (окончательное) состояние или нет. В традиционном алгоритме состояние DFA является состоянием принятия, если любое из состояний NFA было состоянием принятия. Мы изменим это, чтобы сказать, что состояние DFA является состоянием принятия, если и только если:

• = 1 состояние NFA является состоянием принятия, и

• 0 Состояния NFA являются антиприемлемыми.

Этот алгоритм даст нам DFA, который распознает регулярное выражение с предварительным просмотром. Ergo, взгляд в будущее Обратите внимание, что для просмотра сзади требуется отдельное доказательство.

Answer 4

У меня такое ощущение, что здесь задаются два отдельных вопроса:

• Являются ли движки Regex, которые включают в себя "lookaround", более мощными, чем движки Regex, которые этого не делают?
• Предоставляет ли "lookaround" движку Regex возможность разбирать языки, которые являются более сложными, чем языки, сгенерированные из Chomsky Type 3 - Regular грамматика ?

Практический ответ на первый вопрос - да.Lookaround даст движку Regex, который использует эту функцию, существенно больше мощности, чем тот, который этого не делает.Это потому, что он предоставляет более богатый набор «якорей» для процесса сопоставления.Lookaround позволяет вам определить весь Regex как возможную опорную точку (утверждение нулевой ширины).Вы можете получить довольно хороший обзор возможностей этой функции здесь .

Lookaround, хотя и мощный, но не поднимает движок Regex за теоретические пределы, установленные для него грамматикой типа 3,Например, вы никогда не сможете надежно проанализировать язык на основе Context Free - Type 2 Grammar , используя движок Regex, оснащенный lookaround.Движки Regex ограничены мощностью Finite State Automation , и это существенно ограничивает выразительность любого языка, который они могут анализировать, до уровня грамматики типа 3.Независимо от того, сколько «трюков» добавлено в ваш движок Regex, языки, созданные с помощью Context Free Grammar , всегда будут оставаться за пределами его возможностей.Свободный анализ контекста - грамматика типа 2 требует автоматизации нажатия, чтобы «запомнить», где она находится в рекурсивной языковой конструкции.Все, что требует рекурсивной оценки правил грамматики, не может быть проанализировано с помощью движков Regex.

Подводя итог: Lookaround предоставляет некоторые практические преимущества движкам Regex, но не "меняет игру" на теоретическом уровне.

РЕДАКТИРОВАТЬ

Есть ли какая-то грамматика со сложностью где-то между типом 3 (обычный) и типом 2 (контекстно-свободный)?

Я полагаю, что ответ нет,Причина в том, что не существует теоретического ограничения на размер NFA / DFA, необходимого для описания обычного языка.Он может стать произвольно большим и поэтому нецелесообразным для использования (или уточнения).Это где уклоны, такие как "lookaround" полезны.Они предоставляют сокращенный механизм для указания того, что в противном случае привело бы к очень большим / сложным спецификациям NFA / DFA.Они не увеличивают выразительность регулярных языков, они просто делают их более практичными.Как только вы поймете это, станет ясно, что в движки Regex можно добавить множество «функций», чтобы сделать их более полезными в практическом смысле - но ничто не сделает их способными выйти за пределы обычного языка..

Основное различие между языком Regular и Context Free заключается в том, что язык Regular не содержит рекурсивных элементов.Чтобы оценить рекурсивный язык, вам нужна автоматизация Push Down, чтобы «запомнить», где вы находитесь в рекурсии.NFA / DFA не суммирует информацию о состоянии, поэтому не может обрабатывать рекурсию.Поэтому, учитывая нерекурсивное определение языка, для его описания будет некоторое NFA / DFA (но не обязательно практическое выражение Regex).