克莱尼星号
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 \geq 0\,</math>
如果 <math>V</math> 是一个形式语言，集合 <math>V</math> 的第 <math>i</math> 次幂是集合 <math>V</math> 同自身的 i 次串接的简写。
所以在 <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"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}
Kleene 星号应用于字元集合的例子：
- {'a', 'b', 'c'}* = {ε, "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* 被定义为包含 ε(空字符串)并闭合于这个运算下的 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 杰弗里·乌尔曼. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.