正规语言

Cnic.org,开放的网络天书！

正规语言是满足下述相互等价的一组条件的一类形式语言：

可以被确定有限状态自动机识别；
可以被非确定有限状态自动机识别；
可以被只读图灵机识别；
可以用正则表达式描述；
可以用正规文法生成。

正规语言又称正则语言。

例子

所有的有限语言都是正规的。
字母表 {a, b} 上包含奇数个 a 的所有字串构成的语言是正规的。
字母表 {a, b} 上取若干个 a 后紧跟若干个 b形式的所有字串构成的语言是正规的。

[编辑]

封闭性质

这里语言的运算参见条目形式语言。

正规语言的交、并、差、补运算得到的语言仍然是正规语言；
两个正规语言连接﹙把第一个语言的所有字串同第二个语言的所有字串连接起来﹚后得到的语言仍然是正规语言；
正规语言闭包运算后得到的语言仍然是正规语言；
正规语言的每个字串转置后得到的语言仍然是正规语言；
正规语言被任意语言商﹙左商或右商﹚后得到的语言仍然是正规语言。
正规语言代换后得到的语言仍然是正规语言。
与正规语言同态或逆同态的语言仍然是正规语言。

[编辑]

纯代数定义

正规语言也可以以纯粹代数的方式来定义。

Σ 是一个有穷的字母表，Σ* 是 Σ 上的自由幺半群，Σ* 构成了 Σ 上的所有字串。令 M 为一个有限幺半群，映射 f : Σ* -> M 为一个幺半群同态，集合 S 是 M 的一个子集，于是 S 的逆同态象 f^-1(S) 是正规的。每一个正规语言都可以依这种方式来定义。

另外一种定义方式借助于一个等价关系。

取 L 为 Σ* 的任意子集，定义如下的 Σ* 上的等价关系 ~ ： u ~ v，即对Σ* 中所有的的字串w有uw 在 L 中当且仅当 vw 在 L 中。于是对正规语言有下面的结论：语言 L 是正规的当且仅当关系 ~ 的等价类的数量是有限的。在此情况下，等价类的数量就是接受语言 L 的最小确定有限状态自动机的状态数。