[科普中國(guó)]-星高

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

簡(jiǎn)介在數(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

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

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

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

（1）空集合?是正則語(yǔ)言

（2）只包含一個(gè)空字符串的語(yǔ)言{ε}是正則語(yǔ)言

（3）對(duì)所有，{a}是正則語(yǔ)言

（4）若A,B是正則語(yǔ)言，則(kleene星號(hào))都是正則語(yǔ)言

除此之外都不是正則語(yǔ)言

如果一個(gè)語(yǔ)言不是正則語(yǔ)言，它需要一個(gè)存儲(chǔ)器至少是Ω(log logn)的自動(dòng)機(jī)才能辨認(rèn)。換句話說(shuō)，DSPACE(o(log logn))等于所有正則語(yǔ)言的集合。實(shí)際上，大部分的非正則語(yǔ)言需要至少O(logn)的空間。

另見(jiàn)星高問(wèn)題

廣義星高問(wèn)題

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

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