查看“︁Kleene 闭包”︁的源代码

[[分类:形式语言]]
[[分类:字符串]]
[[分类:以 Kleene 命名]]
{{InfoBox
|name=克莱尼闭包
|eng_name=Kleene closure
|aliases=Kleene星号,Kleene星闭包,Kleene<sup>*</sup>运算符,Kleene star,Kleene operator
}}
{{InfoBox
|name=克莱尼正闭包
|eng_name=Kleene plus closure
|aliases=Kleene加号,Kleene正闭包,Kleene<sup>+</sup>运算符,Kleene plus,Kleene<sup>+</sup> operator
}}
'''Kleene闭包'''('''Kleene closure''')指把一个[[字符串]]通过[[连接]]可能构成的全体字符串集合的运算。
也指将一个字符串集（或[[形式语言]]）通过内部元素与连接运算得到的全体可能字符串所构成的新的集合（或形式语言）的运算。

可以理解为这一字符串在连接运算下的最小封闭集合。其中，在原字符串不是空字符串，或者语言中不包含空字符串时，根据构成的是最小[[幺半群]]还是最小[[半群]]，称为 '''Kleene 闭包'''和 '''Kleene 正闭包'''。

== 定义 ==

{{Operation
|name=Kleene闭包
|symbol=<math>^*</math>
|latex=^*
|operand=字符,字符串
|operand_num=1
|result=语言
}}
{{Operation
|name=Kleene正闭包
|symbol=<math>^+</math>
|latex=^+
|operand=字符,字符串
|operand_num=1
|result=语言
}}
对[[字符串]] <math>a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n</math> ，称集合 <math>\{\varepsilon,a,a^2,a^3,\cdots\}=\{a^n\mid n\in\mathbb{N}\}</math> 为字符串的 '''Kleene 闭包'''('''Kleene closure''')，记作 <math>a^*</math> ；称集合 <math>\{a,a^2,a^3,\cdots\}=\{a^n\mid n\in\mathbb{N}^*\}</math> 为字符串的 '''Kleene 正闭包'''('''Kleene plus closure''')，记作 <math>a^+</math> 。

类似地，也为字符 <math>\mathtt{a}</math> 定义 <math>\mathtt{a}^*=\{\mathtt{a}^n\mid n\in\mathbb{N}\}=\{\varepsilon,\mathtt{a},\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{a}\mathtt{a},\cdots\}</math> 和 <math>\mathtt{a}^+=\{\mathtt{a}^n\mid n\in\mathbb{N}^*\}=\{\mathtt{a},\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{a}\mathtt{a},\cdots\}</math> 。

{{Operation
|name=Kleene闭包
|symbol=<math>^*</math>
|latex=^*
|operand=语言
|result=语言
|domain=<math>\mathcal{P}(\Sigma^*)</math>
|codomain=<math>\mathcal{P}(\Sigma^*)</math>
}}
对语言 <math>L</math> ，称语言 <math>L^0 \cup L^1 \cup L^2 \cup \cdots = \bigcup_{n=0}^\infty L^n</math> 为语言的 '''Kleene 闭包'''('''Kleene closure''')，记作 <math>L^*</math> ；称语言 <math>L^1 \cup L^2 \cup \cdots = \bigcup_{n=1}^\infty L^n</math> 为语言的 '''Kleene 正闭包'''('''Kleene plus closure''')，记作 <math>L^+</math>

字符 <math>\mathtt{a}</math> 的（正）闭包和字符串 <math>a</math> 的（正）闭包就是语言 <math>\{\mathtt{a}\}</math> 和 <math>\{a\}</math> 的（正）闭包。

=== 等价定义 ===

对给定字符、字符串或语言，包含给定字符、字符串的，或者包含语言中全体元素的语言中，构成关于字符串的连接运算的最小[[幺半群]]的称为其 '''Kleene 闭包'''('''Kleene closure''')，构成最小半群的称为其 '''Kleene 正闭包'''('''Kleene plus closure''')。

== 性质 ==

* 对字母表 <math>\Sigma</math> 作为语言的 Kleene 闭包就是其上的[[自由幺半群]] <math>\Sigma^*</math> 。
* 正闭包是普通闭包再次连接一次，即 <math>L^+ = L^* L = L L^*</math> ，普通闭包是正闭包补充空串 <math>L^* = L \cup \{\varepsilon\}</math> 。两种闭包相等当且仅当语言中含有空字符串。
* [[幂等律（一元运算）|幂等]]。 <math>(L^*)^*=L^*</math> ， <math>(L^+)^+=L^+</math> 。
* 特殊取值
** [[空语言]] <math>\varnothing</math> ： <math>\varnothing^* = \{\varepsilon\}</math> ， <math>\varnothing^+=\varnothing</math> 
** 空串语言 <math>\{\varepsilon\}</math> ： <math>\{\varepsilon\}^* = \{\varepsilon\}^+ = \{\varepsilon\}</math>


{{字符串}}