正则语言

维基百科，自由的百科全书

跳转到: 导航, 搜索

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

目录

[编辑] 例子

  • 所有的有限语言都是正则的。
  • 字母表 {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（1997）．Introduction to the Theory of Computation．PWS Publishing．ISBN 0-534-94728-X．  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+, 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).
自动机理论: 形式语言和形式文法
乔姆斯基层级 文法 语言 极小自动机
类型 0 无限制 递归可枚举 图灵机
n/a (无公用名) 递归 判定器
类型 1 上下文有关 上下文有关 线性有界
n/a 附标 附标 嵌套堆栈
n/a 树-邻接 适度上下文有关 嵌入下推
类型 2 上下文无关 上下文无关 非确定下推
n/a 确定上下文无关 确定上下文无关 确定下推
类型 3 正则 正则 有限
每个语言或文法范畴都是其直接上面的范畴的真子集。
来自“http://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%AF%AD%E8%A8%80”
个人工具