Kleene星号

更新时间:2023-10-25 15:16

Kleene 星号,或称 Kleene 闭包,德语称 Kleensche Hülle,在数学上是一种适用于字符串符号字符集合一元运算。当 Kleene 星号被应用在一个集合Σ时,写法是Σ*。它被广泛用于正则表达式

定义及标记方法

给定集合V 设:

递归的定义集合Vi+1 ,这里的

所以在 上的 Kleene 星号的定义是

就是说,它是由 中的符号生成的所有可能的有限长度的字符串所构成的集合。

推广

Kleene 星号经常推广到任何幺半群 ,也就是,一个集合 和在 上的二元运算 符合

(封闭性)

(结合律)

(单位元)

如果 是 的子集,则 被定义为包含 (空字符串) 并闭合于这个运算下的 的最小超集。接着 自身是幺半群,并被称为 生成的自由幺半群。这是上面讨论的 Kleene 星号的推广,因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。

例子

Kleene 星号应用于字符串集合的例子:

Kleene 星号应用于字符集合的例子:

参考文献

Kleene 星号的定义基本上可从任何一本自动机理论的参考书中找到。以下是其中一本标准的参考书:

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}