正则表达式（regex）真的很正则吗？
Are regular expressions (regex) really regular?
我知道正则表达式的名字是怎么来的，也看过相关问题(Why are regular expressions called "regular" expressions?)，但我仍然想知道正则表达式是否总是正则的。
比如反向引用怎么才能正则？这是否不需要一些内存，因此不可能由有限状态自动机match/generate？
您引用的问题的答案中的 link 状态（在维基百科中），与现代编程语言提供的许多正则表达式引擎相反，这些引擎增加了允许识别经典正则表达式无法表达的语言.
所以我想说，正则表达式的演变使它偏离了表达常规语言的最初想法。
来自Wikipedia article on regular expressions：
Many features found in virtually all modern regular expression
libraries provide an expressive power that far exceeds the regular
languages. For example, many implementations allow grouping
subexpressions with parentheses and recalling the value they match in
the same expression (backreferences). This means that, among other
things, a pattern can match strings of repeated words like "papa" or
"WikiWiki", called squares in formal language theory. The pattern for
these strings is (.+).
包括反向引用在内的现代扩展使正则表达式系统不再是常规语言的候选者，但是在 IMO 中，它们可以提升为上下文无关语言，但不能提升为图灵机。
常规语法共享一个共同的 属性 称为泵引理。您可以查看示例 here 证明 0n1n 不是常规语法（这与反向引用非常相似).以下是如何证明反向引用不满足泵引理 属性.
当前上下文中的引理：为了表明正则表达式系统是正则语法，需要有一个有限长度 p 使得所有匹配正则表达式且长度等于或大于的字符串p 可以分成三个子字符串 xyz，这样 y 就不是空字符串，并且由 xy*z 表示的所有字符串（y 抽取 [0，无限）次）与正则表达式。
如果我们可以证明没有这样的 p 可以满足正则表达式的条件，那么它不在正则语法中。
对于反向引用，我们将需要两个同样长度的泵送字符串，一个用于捕获组中的子模式，一个用于反向引用。这正是下推自动机或上下文无关语言。还有一个用于上下文无关语法的抽取引理，它基于拆分成 uvwxy，其中 v 和 x 可以被平均抽取 n 次。我们可以证明带有反向引用系统的正则表达式满足这个引理。
我知道正则表达式的名字是怎么来的，也看过相关问题(Why are regular expressions called "regular" expressions?)，但我仍然想知道正则表达式是否总是正则的。
比如反向引用怎么才能正则？这是否不需要一些内存，因此不可能由有限状态自动机match/generate？
您引用的问题的答案中的 link 状态（在维基百科中），与现代编程语言提供的许多正则表达式引擎相反，这些引擎增加了允许识别经典正则表达式无法表达的语言.
所以我想说，正则表达式的演变使它偏离了表达常规语言的最初想法。
来自Wikipedia article on regular expressions：
Many features found in virtually all modern regular expression libraries provide an expressive power that far exceeds the regular languages. For example, many implementations allow grouping subexpressions with parentheses and recalling the value they match in the same expression (backreferences). This means that, among other things, a pattern can match strings of repeated words like "papa" or "WikiWiki", called squares in formal language theory. The pattern for these strings is
(.+).
包括反向引用在内的现代扩展使正则表达式系统不再是常规语言的候选者，但是在 IMO 中，它们可以提升为上下文无关语言，但不能提升为图灵机。
常规语法共享一个共同的 属性 称为泵引理。您可以查看示例 here 证明 0n1n 不是常规语法（这与反向引用非常相似).以下是如何证明反向引用不满足泵引理 属性.
当前上下文中的引理：为了表明正则表达式系统是正则语法，需要有一个有限长度 p 使得所有匹配正则表达式且长度等于或大于的字符串p 可以分成三个子字符串 xyz，这样 y 就不是空字符串，并且由 xy*z 表示的所有字符串（y 抽取 [0，无限）次）与正则表达式。
如果我们可以证明没有这样的 p 可以满足正则表达式的条件，那么它不在正则语法中。
对于反向引用，我们将需要两个同样长度的泵送字符串，一个用于捕获组中的子模式，一个用于反向引用。这正是下推自动机或上下文无关语言。还有一个用于上下文无关语法的抽取引理，它基于拆分成 uvwxy，其中 v 和 x 可以被平均抽取 n 次。我们可以证明带有反向引用系统的正则表达式满足这个引理。