星高

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

• h(∅) = 0, h(ε) = 0, h（a）= 0, ∀ a ∈ A.
• h(E ∪ F) = h（EF）= max(h（E）, h（F）)
• h(Ec) = h（E）
• h(E) = h（E*）+ 1

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

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

另見
*星高問題
*廣義星高問題

注釋