Я видел, как программисты Ruby и Perl выполняют некоторые сложные проблемы с кодом полностью с помощью регулярных выражений. Возможности lookahead и lookbehind в регулярных выражениях Perl делают их более мощными, чем реализации регулярных выражений на большинстве других языков. Мне было интересно, насколько они сильны на самом деле.
Есть ли простой способ доказать или опровергнуть, что регулярные выражения Perl Turing завершены?
За исключением любого встроенного кода, такого как ?{ }, они, вероятно, не охватывают все контекстно-свободные, а тем более Turing Machines. Они могут, но, насколько мне известно, никто так и не доказал это так или иначе. Учитывая, что люди некоторое время пытались решить некоторые проблемы, связанные с контекстом, с регулярными выражениями Perl и еще не придумали решение, вероятно, что они не являются контекстно-зависимыми.
Существует интересная дискуссия о том, какие функции просто удобны, и которые на самом деле добавляют силу. Например, сопоставление 0 n * 1 * 0 n (это обозначение для "любого числа нулей, за которым следует один, за которым следует такое же количество нулей, как и раньше" ) не является чем-то, что можно сделать с чистыми регулярными выражениями. Вы можете доказать, что это не может быть сделано с помощью регулярных выражений с использованием леммы накачки, но простое, неформальное доказательство состоит в том, что регулярное выражение должно было бы подсчитать произвольное количество нулей, а регулярные выражения не могут подсчитывать.
Однако обратные ссылки могут соответствовать таковым:
/(0*) 1 \1/x;
Итак, это означает, что обратные ссылки дают вам больше энергии и не просто удобство. Что еще может дать нам больше силы, интересно?
Кроме того, Perl6 "шаблоны" (они даже не притворяются, что они уже представляют собой регулярные выражения) предназначены для того, чтобы выглядеть похожими на Perl5 regexes (так что вам не нужно много переучивать), но у них достаточно дополнительных функций полностью контекстно-свободный. Они на самом деле разработаны так, что вы можете использовать их, чтобы изменить способ анализа в лексической области.
Есть как минимум два обсуждения: полнота и регулярные выражения Тьюринга и Являются ли шаблоны Perl универсальными? с дальнейшие ссылки.
Консенсус (к моему неподготовленному глазу) кажется, что ответ "нет", но я не уверен, правильно ли я все понимаю.
Для регулярных выражений в Perl существуют два случая:
Каждый обычный язык может быть принят конечным автоматом. Его ввод должен быть конечной строкой.
[...] a детерминированный конечный автомат (DFA), также известный как детерминированный конечный автомат - это машина конечного состояния, которая принимает/отклоняет конечные строки символов [...].
То же самое относится к машинам Тьюринга: формальное определение даже не имеет ввода. Он должен быть закодирован в конечном числе состояний.
Альтернативные (эквивалентные) определения включают ввод, но он должен быть конечным.