我看到Ruby和Perl程序员完全使用正则表达式来完成一些复杂的代码挑战。Perl正则表达式中的前向和后向功能使它们比大多数其他语言中的正则表达式实现更强大。我想知道他们到底有多强大。
是否有一种简单的方法来证明或反驳Perl正则表达式是图灵完备的?
排除任何类型的嵌入式代码，例如?{ }，它们可能无法覆盖所有与上下文无关的代码，更不用说图灵机了。他们可能会，但据我所知，没有人以某种方式证明了这一点。考虑到人们已经尝试用Perl正则表达式解决某些与上下文无关的问题有一段时间了，但还没有提出解决方案，很可能它们不是与上下文无关的。
关于哪些特性仅仅是方便，哪些特性实际上增加了功能，有一个有趣的讨论。例如，匹配0n*1*0n(这是表示"任意数量的零，后面跟着一个1，后面跟着与之前相同数量的零"的符号)不是纯正则表达式可以完成的。您可以使用泵送引理证明这不能用正则表达式完成，但简单的，非正式的证明是正则表达式必须计数任意数量的零，而正则表达式不能计数。
但是，反向引用可以匹配:
/(0*) 1 1/x;
所以这意味着反向引用给你更多的权力，而不仅仅是方便。我在想，还有什么能给我们更多的力量呢?
同样，Perl6"模式"(它们甚至不再假装它们是正则表达式了)被设计成看起来有点像Perl5正则表达式(所以你不需要重新学习太多)，但是它们添加了足够的功能来完全与上下文无关。它们的设计实际上是为了让您可以使用它们来改变在词法范围内解析语言的方式。
至少有两个讨论:图灵完备性和正则表达式和Perl模式是通用的吗?
大家(以我这个外行的眼光来看)似乎都认为答案是否定的，但我不确定我是否理解正确。
Perl中的正则表达式有两种情况:
- 内置代码:当然是图灵完备的。
- 没有嵌入代码:它们总是停止，所以它们不是一般的图灵机。
每一个正则语言都可以被有限自动机接受。其输入必须是一个有限字符串。
[…一个确定性有限自动机(DFA) -也被称为确定性有限状态机是一种接受/拒绝的有限状态机符号的有限字符串[…].
同样适用于图灵机:形式定义甚至没有有输入。它必须以有限的状态进行编码。
可选的(等效的)定义包括输入，但必须是有限的。