正则语言
来自维基百科,自由的百科全书
来自维基百科,自由的百科全书
正则语言又称正规语言是满足下述相互等价的一组条件的一类形式语言:
此条目可参照外语维基百科相应条目来扩充。 |
在字母表集合Σ上的正则语言定义如下:
如果一个语言不是正则语言,它需要一个存储器至少是Ω(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的最小确定有限状态自动机的状态数。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.