我了解正则表达式是如何得名的，并阅读了相关问题（为什么正则表达式称为“正则”表达式？），但我仍然想知道正则表达式是否总是正则表达式。
例如，反向引用如何是常规的？这是否不需要一些内存，因此不可能由有限状态自动机匹配/生成？
问问题
612 次
2 回答
4
您引用的问题的答案中的链接状态（在维基百科中），与现代编程语言提供的许多正则表达式引擎相反，这些引擎增加了允许识别经典正则表达式无法表达的语言的功能。
所以我会说正则表达式的演变使它远离了表达正则语言的最初想法。
几乎所有现代正则表达式库中的许多特性都提供了远远超过正则语言的表达能力。例如，许多实现允许使用括号对子表达式进行分组，并在同一表达式中调用它们匹配的值（反向引用）。这意味着，除其他外，模式可以匹配重复单词的字符串，如“papa”或“WikiWiki”，在形式语言理论中称为正方形。这些字符串的模式是
(.+)\1.
于 2016-03-29T12:01:11.610 回答
3
包括反向引用在内的现代扩展使正则表达式系统不是常规语言的候选者，但是 IMO 可以将它们提升为无上下文语言，但不能提升到图灵机。
正则文法有一个共同的属性，称为泵引理。您可以在此处查看示例，该示例证明 0 n 1 n不是常规语法（与反向引用非常相似）。这是如何证明反向引用不满足泵引理属性的方法。
在当前上下文中抽取引理：为了表明正则表达式系统是正则语法，需要有一个有限长度 p 使得与正则表达式匹配并且长度等于或大于 p 的所有字符串都可以分成三个子字符串 xyz 这样y 不是空字符串，并且由 xy * z 表示的所有字符串（y 泵送 [0, 无限）次）与正则表达式匹配。
如果我们可以证明没有这样的 p 可以满足正则表达式的条件，那么它就不是正则语法。
对于反向引用，我们将需要两个长度相同的泵送字符串，一个用于捕获组中的子模式，一个用于反向引用。这正是下推自动机或上下文无关语言的含义。还有一个用于上下文无关文法的抽水引理，它基于拆分为 uvwxy，其中 v 和 x 可以同样抽水 n 次。我们可以证明带有反向引用系统的正则表达式满足这个引理。
于 2016-03-29T12:18:04.237 回答