regex - 为什么递归正则表达式不是正则表达式？

Question

我正在阅读this question中的一些回复，看到一些人说递归正则表达式不是严格意义上的正则表达式。

为什么是这样？

Answer 1

“严格”的正则表达式描述了正则语言。但是许多特性，例如在表达式本身中使用反向引用或递归，可用于编写接受非正则语言的正则表达式。

例如，描述的语言

(a+)b+\1

不是常规的，因为您不能强制a在 s 之前和之后出现相同的次数b。至少不是常规语言。对于上下文无关甚至上下文敏感的语言，这是完全不同的事情。

然而，仅使用诸如各种量词、字符类等基本事物的正则表达式通常仍然描述正则语言。

Answer 2

所有常规语言都可以被有限自动机识别。有限自动机具有有限数量的状态，因此具有有限的内存（因此得名）。递归“正则”表达式需要潜在的无限堆栈空间来进行递归，因此不可能用有限自动机识别它，因此它不是正则的。

Answer 3

Answer 4

其他答案的基础需要了解所涉及的计算理论。如果您只在编程环境中接触过正则表达式，您可能没有意识到正则表达式也是数学结构。关于正则表达式的维基百科文章可能会为正则表达式的理论方面提供一些背景知识。