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

定義及標記法

編輯

假定

 

遞歸的定義集合

  這裏的  

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

所以在   上的 Kleene 星號的定義是  。就是說,它是從   中的符號生成的所有可能的有限長度的字符串的搜集。

例子

編輯

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,  ),也就是,一個集合 M 和在 M 上的二元運算   有着

  • (閉包)  
  • (結合律)  
  • (單位元)  

如果 VM子集,則 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: