星高

正则语言L的星高定义为所有能表示L的正则表示式的星高的最小值。

简介在数学里，正则表示法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

正则语言L的星高定义为所有能表示L的正则表示式的星高的最小值。

可证明，语言L有星高0当且仅当其语法幺半群为非周期幺半群。

正则语言在字母表集合Σ上的正则语言定义如下：1

（1）空集合Ø是正则语言

（2）只包含一个空字符串的语言{ε}是正则语言

（3）对所有，{a}是正则语言

（4）若A,B是正则语言，则(kleene星号)都是正则语言

除此之外都不是正则语言

如果一个语言不是正则语言，它需要一个存储器至少是Ω(log logn)的自动机才能辨认。换句话说，DSPACE(o(log logn))等于所有正则语言的集合。实际上，大部分的非正则语言需要至少O(logn)的空间。

另见星高问题

广义星高问题

本词条内容贡献者为:

张尉 - 副教授 - 西南大学