正则语言

在理论计算机科学和形式语言理论中，正则语言（也称为理性语言）是一种可以由正则表达式定义的形式语言，在理论计算机科学的严格意义上（与许多现代正则表达式引擎相反，它们被增加了允许识别非正则语言的功能）。另外，正则语言也可以被定义为由有限自动机识别的一种语言。正则表达式和有限自动机的等价性被称为Kleene定理（以美国数学家StephenColeKleene命名）。在乔姆斯基的层次结构中，正则语言是由第三类语法生成的语言。

在一个字母表Σ上的正则语言集合被递归地定义如下。空语言Ø是正则语言。对于每个a∈Σ（a属于Σ），单子语言{a}是正则语言。如果A是正则语言，A*（Kleenestar）是正则语言。因此，空字符串{ε}也是有规律的。如果A和B是有规律的语言，那么A∪B（联合）和A-B（连接）是有规律的语言。Σ以上的其他语言都不是有规律的。关于有规律表达式的语法和语义，请参见有规律表达式。

所有的有限语言都是有规律的，特别是空字符串语言{ε}=Ø*是有规律的。其他典型的例子包括由字母表{a,b}上所有包含偶数个as的字符串组成的语言，或者由所有形式的字符串组成的语言：几个as后面是几个bs。一个不规则语言的简单例子是字符串{anbn|n≥0}的集合。直观地说，它不能被有限自动机识别，因为有限自动机的内存是有限的，它不能记住a的确切数量。下面将给出严格证明这一事实的技术。

一个正则语言满足以下的等效特性。它是正则表达式的语言（根据上述定义）它是非确定性有限自动机（NFA）所接受的语言它是确定性有限自动机（DFA）所接受的语言它可以由正则语法生成它是交替有限自动机所接受的语言它是双向有限自动机所接受的语言。可以由前缀语法生成，可以由只读图灵机接受，可以由单数二阶逻辑定义（Büchi-Elgot-Trakhtenbrot定理），可以由一些有限句法单数M识别。意味着它是有限单体M的子集S在单体同构f下的预像{w∈Σ*|f(w)∈S}。Σ*→M的自由单体在其字母表上的等价类的数量是有限的。(这个数字等于接受L的最小确定性有限自动机的状态数。)属性10.和11.是定义正则语言的纯代数方法；对于单数体M⊆Σ*也可以制定类似的语句。在这种情况下，对M的等价性导致了可识别语言的概念。有些作者用上述不同于1.的属性之一作为正规语言的替代定义。上面的一些等价关系，特别是前四种形式主义中的等价关系，在教科书中被称为Kleene定理。准确地说，哪一个（或哪一个子集）被称为这样的，在不同的作者之间有所不同。有一本教科书称正则表达式和NFA的等价性（上述1.和2.）为Kleene定理。另一本教科书称正则表达式和DFA的等价性（上文1.和3.）为Kleene定理。另外两本教科书首先证明了NFA和DFA的表达等价性（2.和3.），然后将Kleene定理表述为正则表达式和有限自动机（据说后者描述可识别的语言）之间的等价性。

一个以语言学为导向的文本首先将正则语法（上文4.）等同于DFA和NFA，将由这些语言（中的任何一种）生成的语言称为正则，之后它引入了正则表达式，并称其为描述有理语言，最后将Kleene定理陈述为正则和有理语言的重合性。其他作者则简单地将理性表达式和正则表达式定义为同义词，并对理性语言和正则语言做了同样的定义。显然，正则这个词起源于1951年的一份技术报告，其中Kleene介绍了正则事件，并明确表示欢迎任何关于更多描述性术语的建议。诺姆-乔姆斯基（NoamChomsky）在他1959年的开创性文章中，一开始使用了正则这个术语的不同含义（指的是今天所谓的乔姆斯基正则形式），但他注意到他的有限状态语言等同于克莱尼的正则事件。

正则语言在各种操作下是闭合的，也就是说，如果语言K和L是正则的，则其结果也是