克林闭包

  |   0 评论   |   0 浏览

背景

在状态机中涉及到了闭包的概率,网上找到一个例子,讲解的非常的清晰。

符号和符号串

正如我们学习的 English 是由单词和标点符号构成的,单词又是有字母构成的,计算机语言也是如此,也是由字母和数字等一些基本符号构成的,一个源程序就是一个 “基本符号串”,所以我们开始了解符号和符号串相关的定义。

字母表

元素的非空有穷集合。不同的语言有他自己不同的字母表,我们的计算机语言字母表就是数字,字母,标点等若干符号了。中文的字母表就是汉字了。

符号串

字母表的符号组成任何又穷序列的符号串。例如字母表 A={a,b,c} 则由这个字母表组成的符号串包括: {ab,ac,bc,abc,a,b,c}。

有了这些就相当于有了 123456,接下来就是一些运算了,符号串的一些运算了。

连接运算

eg:x=bay=nanaxy=banana(很简单,连接在一起)

方幂运算

x^0= e ; x^1 = x;.....;(和小学数学的方幂一致)

两个字母表乘积:

∑1= {0,1},∑2= {a,b},∑1∑2 = {0a,0b,1a,1b};(小学数学结合运算)

∑的正闭包

∑+=∑∪∑2∪∑3∪∑4∪……

∑的克林闭包(kleene Closure)

∑*=∑0∪∑+(与正闭包区别哦,这算是新概念)

例如:

{0,1}+ = {0,1,00,01,11,000,001,010,011,100,……}

{0,1}* = {ε,0,1,00,01,11,000,001,010,011,100,…}

参考