正则表达式 (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