複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/Kleene星號/9319320
複製
複製成功

Kleene星號

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

目錄

  1. 1 定義及標記方法
  2. 2 推廣
  3. 3 例子
  4. 4 參考文獻

Kleene星號定義及標記方法

給定集合V 設：
  • V0 = {ε} 即只包含空串
  • V1 = V
遞歸的定義集合Vi+1 ，這裏的
  • Vi+1 = { wv: w ∈ Vi and v ∈ V } .
所以在
上的 Kleene 星號的定義是
就是説，它是由
中的符號生成的所有可能的有限長度的字符串所構成的集合。

Kleene星號推廣

Kleene 星號經常推廣到任何幺半羣
，也就是，一個集合
和在
上的二元運算
符合
(封閉性)
(結合律)
(單位元)
如果
是
的子集，則
被定義為包含
(空字符串) 並閉合於這個運算下的
的最小超集。接着
自身是幺半羣，並被稱為
生成的自由幺半羣。這是上面討論的 Kleene 星號的推廣，因為在某個符號的集合上所有字符串的集合形成了一個幺半羣(帶有字符串串接作為二元運算)。

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星號參考文獻

Kleene 星號的定義基本上可從任何一本自動機理論的參考書中找到。以下是其中一本標準的參考書：
  • John Hopcroft | John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.