Rob*_*ert 11 .net regex computer-science turing-machines turing-complete
正则表达式通常被指向不完全转换的语言的经典示例.例如,"正则表达式"作为这个SO问题的答案给出,寻找不是图灵完整的语言.
在我的,或许有点基本的,理解转向完整性的概念,这意味着不能使用正则表达式检查"平衡"的模式.平衡意义具有与结束字符相同数量的开始字符.这是因为要做到这一点需要你有某种状态,以允许你匹配开始和结束字符.
然而,正则表达式的.NET实现引入了平衡组的概念.此构造旨在让您回溯并查看先前的组是否匹配.这意味着.NET正则表达式:
^(?<p>a)*(?<-p>b)*(?(p)(?!))$
可以匹配以下模式:
ab
aabb
aaabbb
aaaabbbb
... etc. ...
这是否意味着.NET的正则表达式是图灵完成的？或者还有其他缺少的东西,这些语言需要图灵完成吗？
在计算理论中,正则表达式描述了常规语言.常规语言类恰好是那些可被某些有限状态机识别或由常规语法生成的语言.但是,您描述的示例(平衡短语)不是常规语言,无法通过有限状态机识别或通过常规语法生成.实际上,这是一个所谓的无上下文语言的教科书示例.这些需要用于识别的下推自动机.无上下文语言类是常规语言的超集,但是是完整语言的适当子集.大多数编程语言的语法(与语义相对)是无上下文的语言.如果您有兴趣了解有关此主题的更多信息,可以从Chomsky层次结构开始