为什么递归正则表达式不是正则表达式？
我在阅读这个问题中的一些回答，看到有些人说递归正则表达式并不严格地讲正则表达式。
为什么是这样？
“严格”正则表达式描述正规语言。 但是，许多功能（例如在表达式本身中使用反向引用或例如递归）可用于编写接受非常规语言的正则表达式。
例如，所描述的语言
(a+)b+1
是不规则的，因为你不能强制a在b s之前和之后出现相同的次数。 至少不是一般的语言。 使用上下文无关或甚至上下文敏感的语言，这是完全不同的问题。
然而，只使用诸如各种量词，字符类等基本事物的正则表达式通常仍然描述常规语言。
所有常规语言都可以被有限自动机识别。 有穷自动机具有有限数量的状态，因此具有有限的存储器（因此名称）。 递归“正则”表达式需要可能无限的堆栈空间来执行递归，因此不可能用有限自动机来识别它，因此它是不规则的。
理论计算机科学对常规语言的严格定义可能看起来很抽象，实际上并没有什么好处，但是如果您有时需要实现状态机来识别某些输入，那么您可以节省大量无用的工作和发卡你可以证明它不能完成。
表达它的一种非正式方式是识别正规语言，不需要任意数量的内存。 常规语言的抽象引理对于证明特定语言（即一组字符串）不能被确定性有限自动机识别是有用的。
Peter Linz的“形式语言与自动机概论”（第115页，第3版）：
定理4.8
设L是一种无限的常规语言。 那么存在一些正整数m，使得任意w∈L且| w | ≥m可以分解为
w = xyz，
同
| XY | ≤m，
和
| Y | ≥1，
这样
wi = xyiz - 等式 （4.2）
对于所有i = 0,1,2，...也是L
为了识别无限语言，有限自动机必须“抽取”或重复其状态的某个部分，这就是yi的功能（对某些字符串重复记号i）。
几乎所有涉及抽象引理的证据都包含矛盾的证据。 在第117页，作者证明语言L = {anbn：n≥0} -ie，形式为aaa ... bbb ...的字符串，其中all-a和all-b子字符串长度相等 - 不是常规的：
假设L是正则的，所以抽要引理必须成立。 我们不知道m的价值，但不管它是什么，我们总是可以选择n = m。 因此，子串y必须完全由a组成。 假设| y | = k。 然后在方程（4.2）中使用i = 0得到的字符串是
w0 = am-kbm
显然不在L中。这与抽象引理矛盾，从而表明L是正则的假设必定是假的。
其他非常规语言的例子：
事实证明，我们松散地调用正则表达式的功能要强大得多：匹配正则表达式和反向引用是NP难！
链接地址: http://www.djcxy.com/p/76745.html