Все ли регулярные выражения останавливаются?
Есть ли регулярное выражение, которое для некоторой входной строки будет искать совпадение всегда?
8 ответов
Для конечного ввода не существует формального регулярного выражения, которое не остановило бы.
Любое формальное регулярное выражение может быть переведено в детерминированные конечные автоматы. DFA читает ввод по одному символу за раз, и в конце ввода вы находитесь либо в принимающем состоянии, либо в неприемлемом состоянии. Если состояние принимает, то ввод соответствует регулярному выражению. В противном случае это не так.
Теперь большинство библиотек "регулярных выражений" поддерживают вещи, которые не являются регулярными выражениями, такие как обратные ссылки. Пока вы держитесь подальше от этих функций и имеете ограниченный ввод, вы гарантированно остановитесь. Если вы этого не сделаете... в зависимости от того, что именно вы используете, вам может быть не гарантирован останов. Perl позволяет вставлять произвольный код, например, и произвольный эквивалентный по Тьюрингу код не гарантирует остановки.
Теперь, если ввод бесконечен, можно найти тривиальные регулярные выражения, которые никогда не остановятся. Например, ".*".
Формальное регулярное выражение - это на самом деле метод описания детерминированного конечного автомата для разбора строк. Регулярное выражение "совпадает", если DFA переходит в принимающее состояние в конце ввода. Поскольку DFA считывает свой вход последовательно, он всегда останавливается, когда достигает конца ввода, и наличие совпадения зависит от того, в каком состоянии DFA он останавливается.
Сопоставление подстрок фактически одинаково, за исключением того, что вместо принудительного прекращения в конце одного чтения строки, DFA вместо этого будет вынужден останавливаться после прочтения каждой возможной подстроки - все еще конечный случай. (Да, большинство движков регулярных выражений реализуют это немного более оптимизированным способом, чем просто выбрасывая каждую возможную подстроку в DFA - но концептуально это ограничение все еще там).
Таким образом, единственный возможный случай, когда DFA не остановился бы, - это если бы ввод был бесконечным, что обычно считается выходящим за рамки проблемы остановки.
Я предполагаю, что невозможно найти регулярное выражение, которое не останавливается.
Размер вашего ввода конечен. Максимальный размер любой подходящей подгруппы регулярного выражения, в максимальном размере, размер вашего ввода.
Если используемый алгоритм не является довольно глупым (многократно повторять случаи), число подходящих подгрупп тоже будет конечным.
Итак, он остановится.
Согласно этому вопросу каждое регулярное выражение останавливается.
Не в том смысле, в котором вы описываете, вы можете иметь некоторые очень неэффективные регулярные выражения, которые отнимают много ресурсов и заканчивают тем, что убивают движок регулярных выражений, это не то же самое, что остановка.
Я не думаю, что остановка действительно применима здесь, как так проницательно отмечали другие комментаторы этого поста. http://en.wikipedia.org/wiki/Halting_problem
Я не могу представить входную строку, которая будет анализироваться вечно, хотя бесконечно длинная строка будет анализироваться вечно. Учитывая, что регулярное выражение может описывать регулярный язык, который потенциально представляет собой бесконечный набор слов, тогда регулярное выражение может описывать язык бесконечных слов, включая слова бесконечной длины. Однако никакая входная строка не может быть бесконечно длинной, поэтому в какой-то момент ее придется остановить.
Например, если a*b принят в языке, и у вас есть бесконечно длинная строка 'a's, тогда да, регулярное выражение никогда не остановится. Однако на практике это невозможно.
+1 за ответ Даниэля: все конечные входы приводят к остановке истинных регулярных выражений (т. Е. Без обратных ссылок или других не-регулярных выражений), и регулярные выражения эквивалентны DFA.
Бонус: сопоставление регулярных выражений может быть простым и быстрым (но медленным в Java, Perl, PHP, Python, Ruby,...)
http://swtch.com/~rsc/regexp/regexp1.html
Обратите внимание, что два графика в верхней части статьи имеют разные масштабы по оси Y: один - секунды, другой - микросекунды!
Да.
Регулярное выражение может быть представлено конечным автоматом. Каждый раз, когда вы получаете атомарный вход, он заставит любой четко определенный FSM перейти в известное состояние.
Исключение составляют случаи, когда у вас бесконечный ввод, но это не относится к проблеме остановки, потому что она имеет дело с конечным вводом. Когда у вас есть конечный автомат и конечный ввод, всегда можно определить, остановится ли ваш компьютер или нет.