正则语言L的星高定义为所有能表示L的正则表示式的星高的最小值。
简介
在数学里，正则表示法 E在有限字母 的 星高定义如下：:
• , .
•
•
•
正则语言L的 星高定义为所有能表示 L的正则表示式的星高的最小值。
可证明，语言 L有星高0当且仅当其语法幺半群为非周期幺半群。
正则语言
在字母表集合上的正则语言定义如下：
（1）空集合是正则语言
（2）只包含一个空字符串的语言是正则语言
（3）对所有，是正则语言
（4）若 A, B是正则语言，则 (kleene星号)都是正则语言
除此之外都不是正则语言如果一个语言不是正则语言，它需要一个存储器至少是的自动机才能辨认。换句话说，DSpace等于所有正则语言的集合。实际上，大部分的非正则语言需要至少的空间。
另见
• 星高问题
• 广义星高问题