解释正则表达式和正则语言的星高
正则表达式(RE)的星高不过是计算理论(TOC)中Kleene星的深度。
例如，
a+b星高为0
(a+b)*星高为1
(a*+b*)*星高为2.......
星高用于表示正则语言和表达式的结构复杂性。
正则表达式可能具有不同的星形高度，这取决于结构复杂性或嵌套。
正则语言的星高是一个唯一的数字，它等于任何代表该语言的正则表达式的最小星高。
正则表达式的星高是出现在表达式中的Kleene星的最大嵌套深度
示例
正则表达式α的星高h(α)由归纳定义为-
h(Φ)=0-----------------1
h(α)=0对于每个α€Σ--------------2
h(α∪β)=h(αβ)=h(α)和h(β)的最大值-----------------3
h(α*)=h(α)+1-----------------4
例如，
如果α=(((ab)*∪b*)*∪a*)那么h(α)=2。
下面给出了找到一个正则表达式的解决方案，该表达式代表相同的语言并且星高尽可能小。
Let the regular expression is ((abc)*ab)* h(α)=h(((abc)*ab)*) =h((abc)*ab)+1 from eq4 =max(h(abc)*,h(a,b))+1 from eq3 =max(h(abc)+1, max(h(a),h(b)))+1 from eq3 and 4 =max(max(h(a),h(bc))+1, max(0,0))+1 =max(max(0,max(h(b),h(c)))+1,0)+1 =max(max(0,max(0,0))+1,0)+1 from eq2 =max(max(0,0)+1,0)+1 =max(0+1,0)+1 =max(1,0)+1 = 1+1 =2