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