查看“︁正则语言”︁的源代码

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

==例子==

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

==定義==

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

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

==封闭性质==

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

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

==纯代数定义==

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

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

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

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

==相关条目==

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

== 引用 ==
* {{cite book|author = {{tsl|en|Michael Sipser||Michael Sipser}} | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | id = 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.

<references />

==外部链接==
* 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 {{Wayback|url=http://www.ucse.edu.ar/fma/sepa/chalchalero.htm |date=20070118144136 }}. 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).

* [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#reg#reg REG at Complexity Zoo]

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

{{形式语言与形式文法}}
[[Category:编译原理]]
[[Category:形式语言|Z]]