Чтобы получить непосредственно к вашему вопросу, вы должны короткое исследование Chomsky Hierarchy. Это старый и красивый способ организации формальных языков в наборах возрастающей сложности. Самая низкая ступень иерархии - это обычные языки. Вы можете догадаться, и вы правы, что RL - это те, которые могут быть представлены «чистыми» регулярными выражениями: те, у кого только алфавит, пустая строка, конкатенация, чередование | и звезда Клейна * (посмотрите Ма, нет обратных ссылок). Классическая теорема теории формального языка - теорема Клейна - состоит в том, что DFA, NFA (как описано в цитированной вами статье) и регулярные выражения имеют точно ту же силу для представления и распознавания языков. Конструкция Томпсона, приведенная в статье, является частью доказательства теоремы.
Каждый RL также является CFL. Но существует бесконечно много CFL, которые не являются регулярными. Функция, которая может существовать в CFL, что делает их слишком сложными, чтобы быть регулярными, - это сбалансированные пары вещей: круглые скобки, начальные блоки и т. Д. Почти все языки программирования - это CFL. CFL могут быть эффективно распознаны так называемым пусковым автоматом Это по существу NFA с стопкой. Стек увеличивается настолько, насколько это необходимо, поэтому он больше не является конечным автоматом. Парсеры реальных языков программирования - это почти все вариации на автоматах выталкивания.
Рассмотрим регулярное выражение с обратной ссылки
^(b*a)\1$
В словах, это представляет собой строки длины 2n для некоторого п, где и n-й и 2n'th персонажи a и все остальные персонажи b. Это прекрасный пример CFL, который не является регулярным. Вы можете строго доказать это с помощью другого крутого инструмента формального языка, называемого леммой о перекачке.
Именно поэтому обратные ссылки вызывают проблемы! Они позволяют «регулярные выражения», которые представляют языки, которые не являются регулярными. Поэтому нет NFA или DFA, которые могут их распознать.
Но подождите, это даже хуже, чем я сделал это до сих пор. Рассмотрим
^(b*a)\1\1$
Теперь у нас есть строка длины 3n, где n-й, 2n'th и 3n'th элементы a и все остальные b. Существует еще один вкус леммы о перекачке, который позволяет доказать, что этот язык слишком сложный, чтобы быть CFL! Никакой пусковой автомат не может распознать этот.
Обратные ссылки позволяют этим перегруженным регулярным выражениям представлять языки, которые являются тремя ступеньками вверх по иерархии Хомского: контекстно-зависимые языки. Грубо говоря, единственный способ распознать CSL - проверить все строки на языке равной длины (по крайней мере, если P! = NP, но это верно для всех практических целей и совсем другой истории). Число таких строк экспоненциально по длине той, которую вы сопоставляете.
Именно поэтому необходим поиск регулярного выражения. Вы можете быть очень умны в том, как вы разрабатываете поиск. Но всегда будет какой-то ввод, который заставляет его принимать экспоненциальное время.
Поэтому я согласен с автором статьи, которую вы цитировали. Можно писать совершенно невинно выглядящие регулярные выражения с no back refs, которые будут эффективно распознаны почти для всех входов, но там, где существует некоторый ввод, который вызывает сопряжение регулярных выражений Perl или Java или Python, потому что это поиск обратного отслеживания - требуется миллионы лет, чтобы завершить матч. Это безумие. У вас может быть сценарий, который является правильным и прекрасно работает в течение многих лет, а затем блокируется в один прекрасный день только потому, что он наткнулся на один из плохих входов. Предположим, что регулярное выражение утопает в синтаксический анализатор сообщений системы навигации в самолете вы верхом ...
Редактировать
По желанию, я эскиз как Насосная лемму можно использовать для доказательства язык a^k b a^k b не является регулярным. Здесь a^k является сокращением на a повторяется k раз. PL говорит, что должно существовать положительное целое число N такое, что каждая строка на регулярном языке длины по крайней мере N должна иметь вид R S T такой, что R S^k T также находится в языке для всех натуральных k. Здесь R, S, T - это строки, а S может быть пустым.
Доказательство PL зависит от того, что каждый правильный язык соответствует некоторому DFA. Допустимый вход в этот DFA длиннее, чем его количество состояний (что соответствует L в лемме) должен вызвать «цикл:», чтобы повторить состояние. Вызовите это состояние X. Машина потребляет некоторую строку R, чтобы получить от начала до X, затем S, чтобы вернуться к X, затем T, чтобы перейти в принимающее состояние.Ну, добавление дополнительных копий S (или удаление S) на входе соответствует только другому числу «циклов» от X до X. Следовательно, будет также принята новая строка с дополнительными (или удаленными) копиями S ,
С каждый RL должен удовлетворять PL, доказательство того, что язык не является регулярным, показывает, что он противоречит PL. Для нашего языка это не сложно. Предположим, вы пытаетесь убедить меня, что язык L = a^k b a^k b удовлетворяет PL. Поскольку он делает это, вы должны уметь дать мне некоторое значение N (см. Выше): количество состояний в гипотетическом DFA, которое распознает L. В этот момент я скажу: «Хорошо, г-н Регулярный парень, рассмотрите строка B = a^N b a^N b. " Если L является регулярным, B должен привести к тому, что этот DFA (независимо от того, как он выглядит) будет зацикливаться на первые N символов, которые должны быть все a s! Таким образом, цикл (строка S выше) состоит также из всех a s. С этим я могу сразу показать, что ваше утверждение о регулярности L является ложным. Я просто решил обойти петлю во второй раз. Это заставит этот гипотетический DFA принять новую строку a^M b a^N b, где M> N, потому что я добавил a s в ее первую половину. Ой! Эта новая строка не находится в L, поэтому PL не является истиной в конце концов. Поскольку я могу делать этот трюк каждый раз, независимо от того, что вы предоставили N, PL не может удерживать L, и L не может быть регулярным в конце концов.
Поскольку это не является регулярным, теорема Клейна говорит нам, что не существует DFA, ни FA, ни «чистого» регулярного выражения, которое его описывает.
Доказательство того, что обратные ссылки допускают языки, которые даже не имеют контекста, имеют очень похожее кольцо, но для этого требуется фон на автоматах, которые я не буду здесь давать. Google предоставит.
NB: Оба они не имеют доказательств того, что задняя часть refs делает признание NP полной. Они просто говорят очень строгим образом, что обратные ссылки добавляют реальную сложность к чистым регулярным выражениям. Они позволяют использовать языки, которые не могут быть распознаны ни на одной машине с конечной памятью, ни с какой-либо бесконечно большой памятью LIFO. Я оставлю доказательство полноты NP другим.
В статье вид ответов, что прямо там, регулярное выражение с backrefs это не регулярное выражение, по его формальному определению. Altho это не отвечает, почему такой быстрый алгоритм не может быть создан для регулярного выражения с backrefs. – Qtax