Perl regexes图灵完整吗？

Question

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

是否有一种简单的方法来证明或证明Perl正则表达式是图灵完整的？

Answer 1

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

关于哪些特征仅仅是方便的,哪些实际上增加了功能,有一个有趣的讨论.例如,匹配0 ⁿ*1*0 ⁿ(这是"任意数量的零,后跟一个,后跟与之前相同数量的零"的表示法)不能用纯正则表达式完成.您可以使用Pumping Lemma证明这不能用正则表达式完成,但简单,非正式的证据是正则表达式必须计算任意数量的零,并且正则表达式不能计数.

但是,反向引用可以与以下内容匹配:

/(0*) 1 \1/x;

这意味着反向引用会给你更多的力量,而不仅仅是方便.我想知道还有什么能给我们更大的力量？

此外,Perl6"模式"(它们甚至不再假装它们是正则表达式)的设计看起来有点像Perl5正则表达式(所以你不需要重新学习很多),但它们有足够的功能添加到完全上下文 - 自由.它们实际上是经过精心设计的,因此您可以使用它们来改变在词法范围内解析语言的方式.

Answer 2

至少有两个讨论:图灵完整性和正则表达式以及Perl模式是否具有普遍性？进一步参考.

对我未经训练的眼睛的共识似乎是答案是"不",但我不确定我是否正确理解了一切.

Answer 3

对于Perl中的正则表达式,有两种情况:

1. 嵌入式代码:它们当然是图灵完备的.
2. 没有嵌入代码:它们总是停止,因此它们不是一般的图灵机.

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

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

这同样适用于图灵机:正式定义甚至不具备输入.它必须以有限数量的状态编码.

替代(等效)定义包括输入,但必须是有限的.