克莱尼星号

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

定義及標記法

假定

$V_{0}=\{\epsilon \}\,$

递归的定义集合

$V_{i+1}=\{wv:w\in V_{i}\wedge v\in V\}\,$ 这里的 $i>0\,$

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

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

例子

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, $\circ$)，也就是，一个集合 M 和在 M 上的二元运算 $\circ$ 有着

• (闭包) $\forall a,b\in M:~a\circ b\in M$
• (结合律) $\forall a,b,c\in M:~(a\circ b)\circ c=a\circ (b\circ c)$
• (单位元) $\exists \epsilon \in M:~\forall a\in M:~a\circ \epsilon =a=\epsilon \circ a$

如果 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.