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

Question

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

Согласно this question, каждое регулярное выражение останавливается.

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

Да.

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

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

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

Answer 8

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

Bonus: Regular Expression Matching может быть простым и быстрым (но медленно в Java, Perl, PHP, Python, Ruby, ...)

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

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