星高

在数学里，正则表示法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 当且仅当其语法幺半群为非周期幺半群。

另见

• 星高问题
• 广义星高问题