regex - Perl 正则表达式图灵完备吗？

Question

我见过 Ruby 和 Perl 程序员完全使用正则表达式来完成一些复杂的代码挑战。Perl 正则表达式中的前瞻和后视能力使它们比大多数其他语言中的正则表达式实现更强大。我想知道他们到底有多强大。

有没有一种简单的方法可以证明或反驳 Perl 正则表达式是图灵完备的？

Answer 1

排除任何类型的嵌入式代码，例如?{ }，它们可能不涵盖所有上下文无关，更不用说图灵机了。他们可能会，但据我所知，实际上没有人以一种或另一种方式证明这一点。鉴于人们一直在尝试使用 Perl 正则表达式解决某些与上下文无关的问题并且还没有提出解决方案，因此它们很可能不是上下文无关的。

关于哪些功能只是方便，哪些功能实际上增加了功能，有一个有趣的讨论。例如，匹配 0 ⁿ *1*0 ⁿ（即“任意数量的零，后跟一个 1，后跟与以前相同数量的零”的符号）不是纯正则表达式可以完成的事情。您可以使用 Pumping Lemma 证明使用正则表达式无法做到这一点，但简单、非正式的证明是正则表达式必须计算任意数量的零，而正则表达式不能进行计数。

但是，反向引用可以匹配：

/(0*) 1 \1/x;

所以这意味着反向引用给你更多的权力，而不仅仅是一种方便。我想知道还有什么能给我们更多的力量？

此外，Perl6“模式”（它们甚至不再假装它们是正则表达式）被设计成看起来有点像 Perl5 正则表达式（所以你不需要重新学习太多），但它们添加了足够的特性来完全上下文 -自由。它们实际上是经过设计的，因此您可以使用它们来改变在词法范围内解析语言的方式。

Answer 2

至少有两个讨论：图灵完整性和正则表达式和Perl 模式是否通用？与进一步的参考。

共识（在我未经训练的眼中）似乎是答案是否定的，但我不确定我是否正确理解了所有内容。

Answer 3

对于 Perl 中的正则表达式，有两种情况：

1. 使用嵌入式代码：它们当然是图灵完备的。
2. 没有嵌入式代码：它们总是停止，因此它们不是通用的图灵机。

每一种常规语言都可以被有限自动机接受。它的输入必须是一个有限的字符串。

[...] 确定性有限自动机 (DFA) — 也称为确定性有限状态机 — 是一种接受/拒绝有限符号串的有限状态机 [...]。

图灵机也是如此：正式定义甚至没有输入。它必须以有限数量的状态进行编码。

替代（等效）定义包括输入，但它必须是有限的。