星高

在理论计算机科学中，更确切地说，在形式语言的理论中，星高是衡量正则表达式和正则语言的结构复杂性的一个标准。一个正则表达式的星高等于该表达式中出现的星的xxx嵌套深度。一个正则语言的星高是该语言的任何正则表达式的最小星高。

更正式地说，有限字母表A上的正则表达式E的星高可以归纳为以下定义。对于A中的所有字母符号a。是表示空集的特殊正则表达式，ε是表示空词的特殊表达式；E和F是任意的正则表达式。正则语言L的星高h(L)被定义为代表L的所有正则表达式中最小的星高。这里的直觉是，如果语言L有大的星高，那么它在某种意义上是内在复杂的，因为它不能通过简单的正则表达式来描述，星高很低。

虽然计算一个正则表达式的星高很容易，但是确定一种语言的星高有时却很棘手。例如，正则表达式然而，所描述的语言只是所有以a结尾的词的集合：因此，该语言也可以通过表达式来描述为了证明这种语言确实具有1的星高，我们仍然需要排除它可以被更低星高的正则表达式所描述。对于我们的例子，这可以通过一个间接证明来完成。我们可以证明，星高为0的语言只包含有限数量的词。由于所考虑的语言是无限的，它不可能是星高为0的。群体语言的星高是可以计算的：例如，{a,b}上的语言的星高是n，其中a和b的出现次数是全等的2n模。

在他对正则语言的星高的开创性研究中，Eggan（1963）建立了正则表达式、有限自动机和有向图的理论之间的关系。我们回顾一下图论和自动机理论的几个概念。在图论中，一个有向图（digraph）G=（V，E）的循环等级r(G)被归纳定义如下。如果G是无环的，那么r(G)=0。如果G是强连接的，E是不空的，那么r(G)=1+是删除顶点v和所有以v开始或结束的边所产生的数字图。如果G不是强连接的，那么r(G)等于G的所有强连接组件中的xxx循环等级。

一组有限的输入符号Σ一组标记的边δ，被称为过渡关系。Q×(Σ∪{ε})×Q。这里ε表示空词。一个初始状态q0∈Q，一组状态F，被区分为接受状态F⊆Q。如果存在一条从初始状态q0到F中某个最终状态的有向路径，并使用δ中的边，使得沿路径访问的所有标签的串联产生单词w，那么，一个单词w∈Σ*就被ε-NFA所接受。

当谈到具有状态集Q的非确定性有限自动机A的数位图特性时，我们自然要讨论由其过渡关系诱导的具有顶点集Q的数位图。正则语言L的星高等于所有具有接受L的ε-过渡的非确定有限自动机中的最小循环等级。