克萊尼星號

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

定義及標記法

假定

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

遞歸的定義集合

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

如果 ${\displaystyle V}$ 是一個形式語言，集合 ${\displaystyle V}$ 的第 ${\displaystyle i}$ 次冪是集合 ${\displaystyle V}$ 同自身的 i 次串接的簡寫。就是說，${\displaystyle V_{i}}$ 可以被理解為是從 ${\displaystyle V}$ 中的符號形成的所有長度為 ${\displaystyle i}$ 的字符串的集合。

所以在 ${\displaystyle V}$ 上的 Kleene 星號的定義是 ${\displaystyle V^{*}=\bigcup _{i=0}^{+\infty }V_{i}=\left\{\varepsilon \right\}\cup V\cup V^{2}\cup V^{3}\cup \ldots }$。就是說，它是從 ${\displaystyle 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, ${\displaystyle \circ }$)，也就是，一個集合 M 和在 M 上的二元運算 ${\displaystyle \circ }$ 有着

• (閉包) ${\displaystyle \forall a,b\in M:~a\circ b\in M}$
• (結合律) ${\displaystyle \forall a,b,c\in M:~(a\circ b)\circ c=a\circ (b\circ c)}$
• (單位元) ${\displaystyle \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 傑弗里·烏爾曼（英語：Jeffrey Ullman）. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.