基本信息

定义及标记方法

推广

基本信息

Kleene 星号，或称 Kleene 闭包，德语称 Kleensche Hülle，在数学上是一种适用于字符串或符号及字符的集合的一元运算。当 Kleene 星号被应用在一个集合V时，写法是V*。它被广泛用于正则表达式。

定义及标记方法

假定

<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 星号经常推广到任何幺半群 (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* 被定义为包含 ε(空字符串)并闭合于这个运算下的 V 的最小超集。接着 V* 自身是幺半群，并被称为 V 生成的自由幺半群。这是上面讨论的 Kleene 星号的推广，因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。