查看“︁克莱尼星号”︁的源代码

'''Kleene 星号'''，或稱'''Kleene 闭包'''，德语稱 Kleensche Hülle，在[[數學]]上是一種適用於[[字符串]]或符號及字元的[[集合 (數學)|集合]]的[[一元運算]]。當 Kleene 星号被應用在一個集合<math>V</math>時，寫法是<math>V^*</math>。它被廣泛用於[[正则表达式]]。

== 定義及標記法 ==
假定
:<math> V_0=\{\epsilon\}\,</math> 
递归的定义集合
:<math> V_{i+1}=\{wv : w\in V_i \wedge v \in V\}\,</math> 这里的 <math>i > 0\,</math>

如果 <math>V</math> 是一个形式语言，集合 <math>V</math> 的第 <math>i</math> 次幂是集合 <math>V</math> 同自身的 i 次[[串接]]的简写。就是说，<math> V_i</math> 可以被理解为是从 <math>V</math> 中的符号形成的所有长度为 <math>i</math> 的[[字符串]]的集合。 

所以在 <math>V</math> 上的 Kleene 星号的定義是
<math> V^*=\bigcup_{i=0}^{+\infty} V_i = \left \{\varepsilon \right\} \cup V \cup V^2 \cup V^3 \cup \ldots</math>。就是说，它是从 <math>V</math> 中的符号生成的所有可能的有限长度的字符串的搜集。

== 例子 ==
Kleene 星号應用於字符串集合的例子：
: {"ab", "c"}* = {&epsilon;, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Kleene 星号應用於字元集合的例子：
: {'a', 'b', 'c'}* = {&epsilon;, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

== 推广 ==

Kleene 星号经常推广到任何[[幺半群]] (''M'', <math>\circ</math>)，也就是，一个集合 ''M'' 和在 ''M'' 上的二元运算 <math>\circ</math> 有着
* ([[闭包 (数学)|闭包]]) <math>\forall a,b \in M:~ a \circ b \in M</math>
* ([[结合律]]) <math>\forall a,b,c \in M:~ (a \circ b) \circ c = a \circ (b \circ c)</math>
* ([[单位元]]) <math>\exists \epsilon \in M:~ \forall a \in M:~ a \circ \epsilon = a = \epsilon \circ a</math>

如果 ''V'' 是 ''M'' 的[[子集]]，则 ''V''* 被定义为包含 &epsilon;(空字符串)并闭合于这个运算下的 ''V'' 的最小[[超集]]。接着 ''V''* 自身是幺半群，并被称为“V 生成的[[自由幺半群]]”。这是上面讨论的 Kleene 星号的推广，因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。

== 参见 ==
* [[克莱尼代数]] 
* [[扩展巴科斯范式]]
* [[泵引理]]
* [[星号高度问题]]，[[广义星号高度问题]]，[[星号无关语言]]
* [[正则表达式]]

==參考文獻==
The definition of Kleene star is found in virtually every textbook on automata theory. A standard reference is the following:
* [[約翰·霍普克洛夫特|约翰·爱德华·霍普克洛夫特]] and {{tsl|en|Jeffrey Ullman|杰弗里·乌尔曼|杰弗里·乌尔曼}}. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.

[[Category:形式语言|K]]