克萊尼星號
Kleene 星號，抑是稱Kleene 閉包，德語稱 Kleensche Hülle，佇數學上是一種適用佇字符串抑是符號佮字元的集合的一元運算。當 Kleene 天星予人應用佇一个集合 $ V $ 時，寫法是 $ V ^ { * } $。伊予人廣泛用佇正則表達式。
定義佮標記法
假定
- $ V _ { 零 }=\ { \ epsilon \ } \ , $
遞歸的定義集合
- $ V _ { i + 一 }=\ { wv : w \ in V _ { i } \ wedge v \ in V \ } \ , $ 遮的 $ i > 零 \ , $
若是 $ V $ 是一个形式語言，集合矣 $ V $ 的第 $ i $ 次冪是集合 $ V $ 仝身體的 i 次串接的簡寫。就是講乎，$ V _ { i } $ 會使予人理解做是對 $ V $ 中的符號形成的所有的長度為 $ i $ 彼字符串的集合按呢。
所以佇咧 $ V $ 上的 Kleene 星號的定義是 $ V ^ { * }=\ bigcup _ { i=零 } ^ { + \ infty } V _ { i }=\ left \ { \ varepsilon \ right \ } \ cup V \ cup V ^ { 二 } \ cup V ^ { 三 } \ 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 星號的推廣，因為佇咧某一个符號的集合頂頭所有字符串的集合形成做一个屘囝半陣 ( 帶有字符串接作為兩箍運算 )。
參見
- 克萊尼代數
- 擴展巴科斯範式
- phóng-phuh引理
- 星號懸度問題，廣義星號懸度的問題，星號無關係語言
- 正則表達式
參考文獻
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 . 一 st edition . Addison-Wesley Publishing Company , 一千九百七十九 .