我正在阅读一些在这个问题中的回答，看到有些人说递归正则表达式严格来说不是正则表达式。
为什么会这样呢？
4个回答
18
“严格”的正则表达式描述正则语言。但是许多特性，例如在表达式本身中使用反向引用或递归等，可以用于编写接受非正则语言的正则表达式。
例如，由以下正则表达式描述的语言
(a+)b+\1
这并不是规则的，因为你不能强制在b之前和之后出现相同次数的a，至少在规则语言中是不行的。但是在上下文无关甚至上下文相关的语言中，情况就完全不同了。
然而，只使用各种量词、字符类等基本元素的正则表达式通常仍描述规则语言。
- Joey
15
所有的正则语言都可以被一个有限状态自动机识别。有限状态自动机具有有限数量的状态，因此只有有限的内存（因此得名）。一个递归的“正则”表达式需要潜在的无限堆栈空间来进行递归，因此不能用有限状态自动机识别，因此它不是正则的。
- Mehrdad Afshari
11
严格的理论计算机科学中，正则语言的定义可能看起来抽象且没有实际用途，但如果你需要实现状态机以识别某些输入，如果你能事先证明无法实现，那么你可以节省很多无用的工作和头发。一种非正式的表达方式是，正则语言的识别不需要任意数量的内存。正则语言的泵引理对于证明特定语言（即字符串集合）不能被确定性有限自动机识别非常有用。
来自Peter Linz（第3版，第115页）的形式语言与自动机简介：
来自Peter Linz（第3版，第115页）的形式语言与自动机简介：
定理 4.8
假设L是一个无限的正则语言。那么存在某个正整数m，使得对于任意满足|w| ≥ m的w ∈ L，都可以分解为
w = xyz,
其中
|xy| ≤ m,
并且
|y| ≥ 1,
这样就有
wi = xyiz — 方程式 (4.2)
对于所有i = 0, 1, 2, …，其也在L中。
要识别无限语言，有限自动机必须“泵”或重复一些状态，这就是yi（表示某个字符串y重复i次的符号）的作用。
几乎所有涉及泵引理的证明都采用反证法。在第117页，作者证明了语言 L = { anbn : n ≥ 0 }——即形如 aaa…bbb… 的字符串，其中所有的 a 和所有的 b 子串长度相等——不是正则的：假设 L 是正则的，因此必须满足泵引理。我们不知道 m 的值，但无论它是多少，我们总可以选择 n = m。因此，子串 y 必须完全由 a 组成。假设 |y| = k。那么，在方程式 (4.2) 中使用 i = 0 得到的字符串为
w0 = am-kbm
很明显，该字符串不属于 L。这与泵引理相矛盾，从而表明假设 L 是正则的必须是错误的。
其他不是正则的语言的例子：
- L = { wwR ：w ∈ Σ* } — 即回文串
- L = { w ∈ Σ* ：na(w) < nb(w) } — 即a的数量少于b的数量
- L = { an! ：n ≥ 0 }
- L = { anbl ：n ≠ l }
- L = { anbl ：n + l 是质数 }
事实证明，我们通常所谓的正则表达式具有相当大的威力：带反向引用的正则表达式匹配是NP-hard！
- Greg Bacon
1
+1。不错的 :-）。其实我讨厌那些证明；我们做了太多了 ;-） - Joey
4
其他答案的基础需要理解涉及计算理论。如果你只接触到正则表达式是在编程环境中，你可能没有意识到正则表达式也是数学构造。维基百科关于正则表达式的文章可能会提供一些有关正则表达式理论方面的背景。
- Jonathon Faust
1
我正在考虑发布这样的答案来补充其他两个（非常好！）答案... :) +1 - Bart Kiers
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接