Kleene星号
在数学上是一种适用于字符串或符号及字符的集合的一元运算
Kleene 星号,或称 Kleene 闭包,德语称 Kleensche Hülle,在数学上是一种适用于字符串符号字符集合一元运算。当 Kleene 星号被应用在一个集合Σ时,写法是Σ*。它被广泛用于正则表达式
定义及标记方法
给定集合V 设:
递归的定义集合Vi+1 ,这里的
所以在 上的 Kleene 星号的定义是
就是说,它是由 中的符号生成的所有可能的有限长度的字符串所构成的集合。
推广
Kleene 星号经常推广到任何幺半群 ,也就是,一个集合 和在 上的二元运算 符合
如果 是 的子集,则 被定义为包含 (空字符串) 并闭合于这个运算下的 的最小超集。接着 自身是幺半群,并被称为 生成的自由幺半群。这是上面讨论的 Kleene 星号的推广,因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。
例子
Kleene 星号应用于字符串集合的例子:
Kleene 星号应用于字符集合的例子:
参考文献
Kleene 星号的定义基本上可从任何一本自动机理论的参考书中找到。以下是其中一本标准的参考书:
参考资料
最新修订时间:2023-10-25 15:16
目录
概述
定义及标记方法
推广
参考资料