什么是正则语言?

[拼音]：zhengze yuyan

[外文]：regular language

形式语言理论中最简单的语言类，是上下文无关语言类的一个真子类，在乔姆斯基语言分层中处于最低层。又称 3型语言。正则语言有两种描述方法：

（1）文法描述；

（2）正则表达式与接受器。正则语言已应用于计算机程序语言编译的词法分析、开关电路设计等方面。

文法描述：正则语言由正则文法（或称右线性文法，见形式语言理论）所生成。当限制产生式形式为A→Bt或A→t时，文法为左线性文法（其中A，B是非终结符，t是终结符）。每一右线性文法必有与之等价的左线性文法存在，即是说，这两种文法生成相同的语言。

正则表达式与接受器：正则语言是正则集，可以用称为正则表达式的简单式子来表示。对任意一个给定的正则表达式可以构造出不确定有限自动机来接收它，反过来，从任意有限自动机可以找出它所接受的正则表达式。

正则表达式描述的语言是正则集。令∑是一个有限集，递归地定义如下：

（1）φ、ε、ɑ(凬ɑ∈∑)是∑上的正则表达式，它们所表示的字集分别为空集，｛ε｝、｛ɑ｝都是正则集。

（2）若 刅、β是∑上的正则表达式，则刅∪β、刅·β、刅*也是∑上的正则表达式，它们所表示的字集｛刅｝、｛β｝、｛刅｝∪｛β｝、｛刅｝｛β｝、｛刅*｝是相应的正则集(运算符∪、·、*分别为并、连接、乘幂闭包。式子里连接符·可以略去不写，运算的优先顺序为：*，·，∪)。

（3）只有有限次使用①、②确定出的表达式才是∑上的正则表达式，只有这些正则表达式所表示的字集才是∑上的正则集。正则集就是正则语言。

为了简化正则表达式，常用下列等式

用①～⑥可以把正则表达式刅写成正则表达式β，即刅与β相似。

正则表达式的导式类似于微积分学中的导式。任一正则表达式刅关于x(∈∑*)的导式Dx刅 递归定义如下：

每一正则表达式只有有限个不相似的导式。表中为正则表达式复杂性的两种测度：H 和N。

泵作用引理:若R是正则语言，则对R中所有字长不小于n的字w＝xyz（y厵ε且xy的字长不超过n）和所有非负整数i必有xyiZ∈R。 这个引理是证明某些语言非正则的有力工具，而且有助于建立算法，以便判断一个给定的有限自动机所接受的语言是有限还是无限的。

对语言运算的封闭性：封闭的意思是将语言运算用到正则集上，其结果仍然是正则集。这对判别某些语言的正则性是有作用的。正则语言类是对并、连接、乘幂闭包运算封闭的最小语言类，并且对于交、补、逆、商、替换、逆同态等运算也封闭。

正则语言的重要结果：与半群（服从结合律的二元运算的非空集），态射、直积等抽象代数的概念相联系已形成学科性的课题，已经得到的重要结果有：

（1）R吇∑*，R 是正则语言的等价条件为：∑*关于右同余关系ER的等价类类数有限等价关系ER规定为：x，y∈∑*，xERy当且仅当对每一Z∈∑*或者xz与yz都在R中或者都不在R 中。

（2）R 的语法么半群MR的元素个数有限(幺半群是有幺元的半群，幺元类似于数 1对数的乘法所起的作用，例如∑*对连接运算构成一个半群，由于对任意x∈∑*，xε＝εx＝x，故空字ε 就是∑*的幺元，因而∑*是一个幺半群)。幺半群∑*到PF(Q)的态射f下的象MR就是R的语法幺半群，其中PF(Q)是Q到Q的全体偏函数（即对Q的元不一定都有定义的函数）对函数合成运算构成的幺半群，Q是接受语言R 的自动机M的状态集合，态射f的定义为f:x→嗞x，

式中δ是M的状态转移函数。

（3）对每一正则语言R都存在同态映射h1、h2、h3、h4使


上的语言。

（4）正则语言的星流形与有限幺半群流形之间有一一映射存在，这是塞缪尔·爱伦堡定理。若干正则语言形成的族在布尔运算、派生、逆同态下封闭时就是一个星流形。若干有限幺半群形成的族在态射象、子幺半群、有限直积下封闭时就是一个幺半群流形。

参考书目

M. A. Arbib， Theories of Abstract Automata，PrenticeHall， Englewood Cliffs， N. J.， 1969.