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

Question

Существует ли какое-либо регулярное выражение, которое для некоторой входной строки будет всегда искать совпадение?

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

Да.

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

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

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

Answer 8

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

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