正则语言

正则语言又称-{zh-cn:正规语言; zh-tw:正則語言; zh-hk:正規語言;}-是满足下述相互等价的一组条件的一类形式语言：
*可被确定有限状态自动机识别；
*可被非确定有限状态自动机识别；
*可被只读图灵机识别；
*可用正则表达式描述；
*可用正则文法生成。
*可用前缀文法生成。

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

定義
在字母表集合Σ上的正規語言定義如下：
*空集合Ø是正規語言
*只包含一個空字串的語言{ε}是正規語言
對所有a \in \Sigma，{a*}是正規語言
若A, B是正規語言，則 A\cdot B, A\bigcup B, A^(kleene星号)都是正規語言
*除此之外都不是正規語言

如果一個語言不是正規語言，它需要一個記憶體至少是Ω(log log n)的自動機才能辨認。換句話說，DSPACE(o(log log n))等于所有正規語言的集合。實際上，大部份的非正規語言需要至少O(log n)的空間。

封闭性质
这里语言的运算参见条目形式语言。

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

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

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

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

取L为Σ的任意子集，定义如下的Σ上的等价关系~ (叫做“语法关系”)：
u ~ v，即对Σ中所有的的字串w有uw在L中当且仅当vw在L中。于是对正规语言有下面的结论：语言L是正规的当且仅当关系~的等价类的数量是有限的（其证明在条目语法幺半群中）。在此情况下，等价类的数量就是接受语言L*的最小确定有限状态自动机的状态数。

评论 (0)