星高✍️

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

简介

在数学里，正则表示法 E在有限字母 的 星高定义如下：:

• , .

• 

• 

• 

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

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

正则语言

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

（1）空集合是正则语言

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

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

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

除此之外都不是正则语言如果一个语言不是正则语言，它需要一个存储器至少是的自动机才能辨认。换句话说，DSpace等于所有正则语言的集合。实际上，大部分的非正则语言需要至少的空间。

另见

• 星高问题

• 广义星高问题

参考资料