解釋字母表在計算理論中的能力。

如果Σ是一個字母表，所有字串的集合可以用指數表示法表示為該字母表中一定長度的字串。字母表的冪用Σk表示，它是長度為k的字串的集合。

例如：

• Σ ={0,1}
• Σ¹= {0,1} ( 2¹=2)
• Σ²= {00,01,10,11} (2²=4)
• Σ³= {000,001,010,011,100,101,110,111} (2³= 8)

字母表Σ上的字串集合通常用Σ*（克萊尼閉包）表示

例如，Σ*= {0,1}*

={ ε,0,1,00,01,10,11,………}

因此，Σ*= Σ0U Σ1U Σ2U Σ3…………. 包含ε符號

字母表Σ上的字串集合（不包含ε）通常用Σ⁺（克萊尼加法）表示。例如，Σ⁺={0,1}⁺

={0,1,00,10,01,11,…………}

因此，Σ⁺= Σ*- { ε}

或者

Σ⁺= Σ¹U Σ²U Σ³…………. 不包含ε符號

字母表的冪有兩種型別，解釋如下：

• 克萊尼閉包 (Σ*)
• 克萊尼加法 (Σ⁺)

克萊尼閉包: Σ*

設 Σ ={a,b}

Σ*= Σ⁰U Σ¹U Σ²U Σ³…………

={ε} U {a,b} U {aa,ab,ba,bb}...........

包含空字串ε的全部字串集合稱為克萊尼閉包。

克萊尼加法:Σ⁺

設 Σ ={a,b}

Σ⁺= Σ¹U Σ²U Σ³…………

={a,b} U {aa,ab,ba,bb}...........

不包含空字串ε的全部字串集合稱為克萊尼加法。

Σ⁺= Σ*- { ε}

或者

Σ⁺= Σ¹U Σ²U Σ³

Bhanu Priya

更新於: 2021年6月11日

5K+ 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始學習