正则语言

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

例子

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

定義

在字母表集合Σ上的正規語言定義如下：
空集合Ø是正規語言
只包含一個空字串的語言{ε}是正規語言
對所有，{a}是正規語言
若A, B是正規語言，則(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的最小确定有限状态自动机的状态数。

相关条目

 形式语言
 有限状态自动机
 正则表达式
 正则文法
 乔姆斯基体系

 引用 
  Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.

外部链接
 Department of Computer Science at the University of Western Ontario: Grail+, https://web.archive.org/web/20060404094049/http://www.csd.uwo.ca/Research/grail/. A software package to manipulate regular expressions, finite-state machines and finite languages. Free for non-commercial use.

 Chalchalero! http://www.ucse.edu.ar/fma/sepa/chalchalero.htm . A free visual software to manipulate regular expressions, regular grammars, finite-state machines and finite languages developed by the SEPa! Project Team (Universidad Católica de Santiago del Estero).

 REG at Complexity Zoo

 https://web.archive.org/web/20060404094049/http://www.csd.uwo.ca/Research/grail/ ：西安大略大学计算机科学系Grail+， 一个可以操作正则表达式、有限状态自动机和有限语言的自由软件包。

Category:编译原理
Z