[科普中國]-星高

正則語言L的星高定義為所有能表示L的正則表示式的星高的最小值。

簡介在數(shù)學(xué)里，正則表示法E在有限字母A的星高h（E）定義如下：:

h(?) = 0,h(ε) = 0,h（a）= 0, ?a∈A.

h(E∪F) =h（EF）= max(h（E）,h（F）)

h(E0) =h（E）

h(E*) =h（E）+ 1

正則語言L的星高定義為所有能表示L的正則表示式的星高的最小值。

可證明，語言L有星高0當(dāng)且僅當(dāng)其語法幺半群為非周期幺半群。

正則語言在字母表集合Σ上的正則語言定義如下：1

（1）空集合?是正則語言

（2）只包含一個空字符串的語言{ε}是正則語言

（3）對所有，{a}是正則語言

（4）若A,B是正則語言，則(kleene星號)都是正則語言

除此之外都不是正則語言

如果一個語言不是正則語言，它需要一個存儲器至少是Ω(log logn)的自動機才能辨認。換句話說，DSPACE(o(log logn))等于所有正則語言的集合。實際上，大部分的非正則語言需要至少O(logn)的空間。

另見星高問題

廣義星高問題

本詞條內(nèi)容貢獻者為:

張尉 - 副教授 - 西南大學(xué)