正则语言

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

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

例子

• 所有的有限语言都是正则的。
• 字母表{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的最小确定有限状态自动机的状态数。

相关条目

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

引用

• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6.  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+， 一个可以操作正则表达式、有限状态自动机和有限语言的自由软件包。