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

Question

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

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

Answer 1

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

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

One Pebble 2-NFA (см. Раздел "Введение" к этой статье).

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

Вступление

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

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

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

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

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

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

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

Итак, для просмотра в форме u (?= V) w

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

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

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

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

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

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

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

и строка abbb.

У нас есть abbb, который проходит через peb2nfa для a (?=... b), в конце которого мы находимся в состоянии: (bbb, matched) (то есть во входных данных bbb остается, и он соответствует 'a' сопровождаемый '..b'). Теперь из-за * мы возвращаемся к началу (см. Конструкцию в ссылке выше) и вводим 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, поскольку вы concat, числа гальки r1 должны увеличиваться на глубину r. Для r* и r|r1 нумерация гальки остается неизменной.

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

Заключение

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

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

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

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

Answer 2

Ответ на заданный вами вопрос о том, можно ли распознать больший класс языков, чем обычные языки с помощью регулярных выражений, дополненных 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 вы можете найти регулярное выражение rs, которое соответствует тем выражениям, которые соответствуют 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), что означает, что вы не можете перевести взгляд из контекста, в котором вы его нашли, - вам нужно обработать всю строку. Я предполагаю, что это делает неприятным для людей работать и разрушает интуицию людей относительно регулярных выражений.

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

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

Приношу свои извинения за неясность: я не верю, что вы можете дать подтверждение регулярности регулярных выражений + обходных путей путем структурной индукции, мой пример 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](ab)*[^a]|a(ab|[^a])*b)b)*$

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

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

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

Приношу свои извинения за то, что не поставил конструкцию.

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

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

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))+, что является несколько упрощенной версией регулярного выражения, которое я предложил в комментариях к доказательству Фрэнсиса. Если мы используем мою конструкцию вместе с традиционными конструкциями Томпсона, мы получим:

es - это эпсилон-переходы (переходы, которые могут быть приняты без использования какого-либо ввода), а состояния антиприятия помечены 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 с "внешним видом" более мощными, чем движки Regex?
• Предоставляет ли "lookaround" движок Regex возможность разбирать языки, которые являются более сложными, чем те, которые созданы с помощью грамматики Chomsky Type 3 - Regular?

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

Lookaround, хотя и мощный, не поднимает движок Regex за теоретические пределы, установленные для него грамматикой типа 3. Например, вы никогда не сможете надежно проанализировать язык на основе контекстно-свободной грамматики типа 2, используя движок Regex, оснащенный поиском. Движки Regex ограничены возможностями конечной автоматики, и это существенно ограничивает выразительность любого языка, который они могут анализировать, до уровня грамматики типа 3. Независимо от того, сколько "уловок" добавлено в ваш движок Regex, языки, созданные с помощью контекстно-свободной грамматики, всегда будут оставаться за пределами ее возможностей. Свободный анализ контекста - грамматика типа 2 требует автоматизации нажатия, чтобы "запомнить", где она находится в рекурсивной языковой конструкции. Все, что требует рекурсивной оценки правил грамматики, не может быть проанализировано с помощью движков Regex.

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

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

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

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

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