正则语言

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

正则语言

正则语言正则语言又称-{zh-cn:正规语言; zh-tw:正则语言; zh-hk:正规语言;}-是满足下述相互等价的一组条件的一类形式语言：定义. 在字母表集合Σ上的正规语言定义如下：如果一个语言不是正规语言，它需要一个记忆体至少是Ω(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"的最小确定有限状态自动机的状态数。

美洲

望城区

黄宝石 (1969年电影)

克劳德·杰德

9月11日

约翰·济慈

南宁市

桂林市

柳州市

梧州市

北海市

玉林市