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