解釋正則表示式和正則語言的星高

正則表示式（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 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始學習