.net - .NET 的正则表达式图灵完整吗？

Question

正则表达式通常被认为是未完成语言的经典示例。例如，“正则表达式”作为此 SO 问题的答案 looking for languages that are not Turing complete .

在我对转向完整性概念的理解中，也许有些基本，这意味着不能使用正则表达式来检查“平衡”的模式。平衡含义的开头字符数与结尾字符数相同。这是因为这样做需要您拥有某种状态，以允许您匹配开始和结束字符。

然而，正则表达式的 .NET 实现引入了 balanced group 的概念。 .此构造旨在让您回溯并查看前一组是否匹配。这意味着 .NET 正则表达式:

^(?<p>a)*(?<-p>b)*(?(p)(?!))$

可以匹配以下模式:

ab
aabb
aaabbb
aaaabbbb
... etc. ...

这是否意味着 .NET 的正则表达式是图灵完备的？或者是否还缺少其他使语言图灵完备所需的东西？

Answer 1

在计算理论中，正则表达式描述了一种正则语言。正则语言类正是那些可以被某些有限状态机识别或由正则文法生成的语言。但是，您描述的示例(平衡短语)不是常规语言，无法被有限状态机识别或由常规语法生成。事实上，这是所谓的上下文无关语言的教科书示例。这些需要下推自动机进行识别。上下文无关语言类是常规语言的超集，但也是图灵完备语言的适当子集。大多数编程语言的语法(相对于语义)是一种上下文无关语言。如果您有兴趣了解有关此主题的更多信息，可以从 Chomsky hierarchy 开始