什么是规律性？

Question

这是一个计算机科学问题,而不是编程问题,但我认为这是所有相关网站中最好的问题.

当我发现正则表达式并查找该术语时,我认为这种"规律性"属性指的是表达式语言具有可定义的结构模式.然而,在阅读有关主题及其背后的理论时,我了解到有些语言不规则,但从定义它们的方式来看,很清楚模式可以与它们匹配.一种这样的语言是(a ^ n)(b ^ n).显然这是一种模式,但这不是一种常规语言.所以现在我想知道常规语言是什么使它们成为常规语言,这种语言不是吗？

Answer 1

直观地解释计算机科学是......棘手的.我会试一试,但请记住,其中一些将"足够接近"但理论上并不严谨.

常规语言是可以由计算机等同于有限自动机(DFA/NDFA)的机器决定的语言.有限自动机可以被认为是纯粹在状态下运行的机器,没有存储.所以,你可以看到一个^ñ b ^ň不能经常因为它需要一台能够计算A和B的数量(因此必须有无限*存储容量),以便对它们进行比较.

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

要获得更严格(并且相应更密集的视图),请查看维基百科文章和链接页面.

_{*无限在这里无所谓,但我提到完整性.可能更容易将其视为"幸运,总是足够"的存储.}

Answer 2

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