星高

在數學裏，正則表示法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^c) = h（E）
• h(E^*) = h（E）+ 1

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

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

另見

• 星高問題
• 廣義星高問題