正则表达式通常被指向为不完成语言的典型例子.例如,“正则表达式”作为这个SO问题
looking for languages that are not Turing complete的答案.
在我可能有点基本的理解转化完整性的概念中,这意味着不能使用正则表达式来检查“平衡”的模式.平衡意义具有相等数量的开头字符作为关闭字符.这是因为这样做会要求你有某种状态,让你匹配打开和关闭的字符.
然而,正则表达式的.NET实现引入了balanced group的概念.这个结构旨在让您回溯,并查看以前的组是否匹配.这意味着.NET正则表达式：
^(?<p>a)*(?<-p>b)*(?(p)(?!))$
可以匹配一个模式：
ab aabb aaabbb aaaabbbb ... etc. ...
这是否意味着.NET的正则表达式是图灵完成？还是还有其他一些缺少的语言成为图灵完成所需要的东西？
在计算理论中,正则表达式描述了一种常规语言.正规语言的类正是那些可以由某些有限状态机识别或由常规语法产生的语言.但是,您所描述的例子(平衡短语)不是常规语言,无法被有限状态机识别或由常规语法生成.其实这是一本教科书的例子,称之为无上下文的语言.这些需要一个下推自动机才能识别.无上下文语言的类是普通语言的超集,而是完整语言的一个适当子集.大多数编程语言的语法(而不是语义)是无上下文的语言.如果您有兴趣了解有关此主题的更多信息,您可以从
Chomsky hierarchy开始
