computer-science - 什么是规律性？

Question

这更像是一个计算机科学问题而不是编程问题，但我认为这是所有相关网站中最好的提问地点。

当我发现正则表达式并查找该术语时，我认为这种“正则性”属性是指表达式的语言具有可定义的结构模式这一事实。然而，在阅读主题和这背后的理论时，我了解到有些语言是不规则的，但从它们的定义方式来看，很明显可以将模式与它们匹配。一种这样的语言是 (a^n)(b^n)。显然这是一种模式，但这不是一种常规语言。所以现在我想知道是什么让常规语言成为常规语言，而这种语言不是？

Answer 1

直观地解释计算机科学是……棘手的。我会试一试，但请记住，其中一些将“足够接近”但在理论上并不严格。

常规语言是一种可以由计算机决定的语言，该机器在计算上等效于有限自动机 (DFA/NDFA)。有限自动机可以被认为是一台纯粹在状态下运行的机器，没有存储空间。所以你可以看到 a ⁿ b ⁿ不能是规则的，因为它需要一台可以计算 a 和 b 数量的机器（因此必须具有无限*存储容量）才能比较它们。

为了比较，(abc) ⁿ 是规则的，因为重复的次数无关紧要。

如需更严格（以及相应更密集的视图），请查看维基百科文章和链接页面。

_{*这里的无限无关紧要，但为了完整起见，我提到它。将其视为“幸运的是，总是足够”的存储可能更容易。}

Answer 2

该名称的词源来自 Kleene 1950 年代使用他为此目的创建的数学符号描述规则集的工作。看到这个。

Answer 3

也许关于常规语言的维基百科文章可以比我们更好地解释它。不过，我会试一试。

从理论的角度来看，常规语言（字符串集）是一种可以使用有限状态自动机生成的语言。用程序员的话来说，这相当于说可以用正则表达式生成。因此，所有有限语言（字符串集）都是正则的，但也有一些无限语言，例如 a ⁿ b ⁿ（所有 n a 后跟 n b 的字符串的语言）无法使用 FSA 或正则识别表达式。有更强大的计算设备（例如使用图灵机建模的现代计算机）可以识别这些语言。

正则表达式在编程中用于字符串搜索的原因如此之多，因为它们可以识别对我们程序员很重要的绝大多数字符串，同时可以使用有限状态自动机实现非常快速的搜索。

Answer 4

in这个词regular是regular expression指正则的数学概念，而不是英文概念。就像prime数学中的这个词与素牛肉几乎没有关系一样。

它被 CS（它是数学的一个分支）继承来引用一个更具体的概念：http ://en.wikipedia.org/wiki/Regular_language

Answer 5

正则表达式并不是真正的正则，名称是词源。