解释正则表达式和正则语言的星高

正则表达式（RE）的星高只不过是计算理论（TOC）中克莱尼星的深度。

例如，

• a+b 的星高为 0
• (a+b)* 的星高为 1
• (a*+b*)* 的星高为 2 …….

星高用于表示正则语言和表达式的结构复杂度。

正则表达式可能具有不同的星高，这取决于结构复杂度或嵌套。

正则语言的星高是一个唯一的数字，它等于表示该语言的任何正则表达式的最小星高。

正则表达式的星高是表达式中出现的克莱尼星的最大嵌套深度。

示例

正则表达式 α 的星高 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

Bhanu Priya

更新于： 2021年6月12日

470 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始学习