克莱尼星号

维基百科,自由的百科全书
跳转至: 导航搜索

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 有着

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