解释字母表在计算理论中的能力。

如果Σ是一个字母表，所有字符串的集合可以用指数表示法表示为该字母表中一定长度的字符串。字母表的幂用Σ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+ 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习