Все ли регулярные выражения останавливаются?

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

Любое формальное регулярное выражение может быть преобразовано в детерминированный конечный автомат. DFA считывает ввод по одному символу за раз, и в конце ввода вы либо находитесь в принимающем состоянии, либо в не принимающем состоянии. Если состояние принимает, то входные данные соответствуют регулярному выражению. В противном случае это не так.

Сейчас большинство библиотек «регулярных выражений» поддерживают вещи, которые не являются регулярными выражениями, например обратные ссылки. Пока вы держитесь подальше от этих функций и имеете ограниченный ввод, остановка вам гарантирована. Если вы этого не сделаете ... в зависимости от того, что именно вы используете, остановка вам может не быть гарантирована. Perl позволяет, например, вставлять произвольный код, а остановка произвольного кода, эквивалентного машине Тьюринга, не гарантируется.

Теперь, если ввод бесконечен, можно найти тривиальные регулярные выражения, которые никогда не остановятся. Например, «.*».

Формальное регулярное выражение - это фактически метод описания детерминированного конечного автомата для анализа строк. Регулярное выражение «совпадает», если DFA переходит в состояние приема в конце ввода. Поскольку DFA считывает свой ввод последовательно, он всегда будет останавливаться, когда достигнет конца ввода, и, есть ли совпадение, просто вопрос проверки того, в каком состоянии DFA он останавливается.

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

Таким образом, единственный возможный случай, в котором DFA не остановился бы, - это если бы вход был бесконечным, что обычно считается выходящим за рамки проблемы остановки.

Я полагаю, невозможно найти регулярное выражение, которое не останавливается.

Размер вашего ввода конечен. Максимальный размер любой совпадающей подгруппы регулярного выражения равен максимальному размеру вашего ввода.

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

Итак, он остановится.

Согласно этому вопросу, каждый регулярное выражение останавливается.

Не в том смысле, который вы описываете, у вас могут быть очень неэффективные регулярные выражения, которые занимают много ресурсов и в конечном итоге убивают механизм регулярных выражений, это не то же самое, что остановка.

Я не думаю, что здесь действительно применима остановка, как проницательно отметили другие комментаторы этого поста. http://en.wikipedia.org/wiki/Halting_problem

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

Например, если в языке допускается a * b, и у вас есть бесконечно длинная строка из «a», тогда да, регулярное выражение никогда не остановится. Однако на практике это невозможно.

да.

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

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

http://en.wikipedia.org/wiki/Finite_state_machine

+1 за ответ Даниэля: все конечные входы вызывают остановку истинного регулярного выражения (то есть без обратных ссылок или других функций, отличных от регулярного), а регулярные выражения эквивалентны DFA.

Бонус: сопоставление регулярных выражений может быть простым и быстрым (но медленным в Java, Perl, PHP, Python, Ruby, ...)

http://swtch.com/~rsc/regexp/regexp1.html

Обратите внимание, что два графика в верхней части статьи имеют разные масштабы по оси Y: один - секунды, другой - микросекунды!