星高

簡介

在數學裡，正則表示法 E在有限字母 A的 星高 h（ E）定義如下：:

•h(∅) = 0,h(ε) = 0,h（a）= 0, ∀a∈A.

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

•h(E) =h（E）

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

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

可證明，語言 L有星高0若且唯若其語法么半群為非周期么半群。

正則語言

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

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

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

星高

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

星高

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

除此之外都不是正則語言

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

另見

•星高問題

•廣義星高問題