计算机科学

首页 > 计算机科学

克莱尼星号

2018-08-30 10:01:43     所属分类:形式语言

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

目录

  • 1 定义及标记法
  • 2 例子
  • 3 推广
  • 4 参见
  • 5 参考文献

定义及标记法

假定

递归的定义集合

这里的

如果 是一个形式语言,集合 的第 次幂是集合 同自身的 i 次串接的简写。就是说, 可以被理解为是从 中的符号形成的所有长度为 的字符串的集合。

所以在 上的 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 星号经常推广到任何幺半群 (M, ),也就是,一个集合 M 和在 M 上的二元运算 有着

  • (闭包)
  • (结合律)
  • (单位元)

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

  • John Hopcroft|John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.

上一篇:克莱尼代数
下一篇:形式语言
相关推荐