非确定性和Kleene定理

语言与计算理论导引 非确定性和Kleene定理4 非确定性和Kleene定理4.1 非确定型有限自动机为了证明正则语言等价于能够被FA识别的语言，我们先对FA作一些方便性的扩充。仍然具有有限的状态数，且识别语言的能力保持不变。一些限制放宽了，更容易构造和解释。例子4.1图4-1a显示了例子3.14构造的FA，它接受的语言是(11+110)*0，图4-1b显示了一个不同于一般FA的例子，状态q4没有转移箭头，而状态q0在输入字符为1时有两个转移箭头。状态q4没有转移箭头，含义是不存在一个起始字符为a（本例为0或1）的输入字符串能够使得状态从q4转移到某个接受状态，我们可以增加一个失败（或死，dead）状态f，对于输入字符a，状态q4转移到f，失败状态的含义是只有进入没有离开的转移箭头。显然任何被成功接受的字符串都不会进入失败状态，因此为了简化图面，往往省略失败状态，而不会影响自动机的接受能力。状态q0在同一个输入字符时有多个转移箭头，看起来是对传统FA的很大的突破。我们无法象传统FA机那样线性地记录字符串在FA中的转移过程，而在某些步骤出现了歧义，因此FA机要并行地运算各种可能。但这种带多向转移的图似乎更适合正则表达式，比如图4-1b，从q0到q0有两个循环，一个表示的字符串是(11)*，另一个表示的是(110)*，综合起来，从q0到q0的字符串是(11+110)*，则从q0到q4的字符串是(11+110)*0。反过来，根据正则表达式(11+110)*0也能够很直观地画出相应的带多向转移的FA。由于同一个字符串可能带来FA多个状态转移路径，因此现在问题变成，是否存在一条到达接受状态的路径，这类似于根据正则表达式生成字符串，某些步骤可以有多种尝试，只要其中一种尝试生成了字符串，则认为该字符串符合这个正则表达式。因此这类FA给正则语言的分析引入了一个新的概念，即猜测尝试。现在不考虑这种具体实现的问题，而考虑如何形式化定义这类FA。我们只需要修改（或扩充）传统FA的转移函数的定义。传统的转移函数输入一个字符，转移到一个状态，即Q中的一个元素，例子4.1中的转移函数则转移到0个或多个状态，即Q的一个子集，包括空集。我们称这种转移函数是非确定的，而这样的FA称为非确定型FA（nondeterministic FA, NFA），而传统的FA称为确定型FA（deterministic FA, DFA）。目前我们看起来NFA比DFA要强大很多，以后将证明任何一个NFA都能构造一个完全模拟它的DFA，因此非确定型没有增强FA的能力。定义4.1 非确定型有限自动机（NFA）是一个5元组，M=（Q, , q0, d, A），Q和是非空有限集，q0Q，AQ，转移函数定义为： d: Qx2Q2Q是Q的幂集，即所有Q的子集组成的集合，则函数d的值从确定型的一个状态放松成一个状态集。思考：初始状态可不可以由一个状态扩充成一个状态集？类似地扩充连续转移函数（或称字符串的转移函数）d*的定义，其形式仍然是：d*(p, xa) = d(d*(p, x), a)自然想到用递归定义，首先，空串不影响状态变迁，但转移函数的值是一个集合，而不是单个状态，因此：d*(p, L)=p而对于非空字符串x=a1a2.an，d*(p, x)的值也应该是一个集合，设qd*(p, x)，含义是存在一个状态路径：p0, p1, ., pn，其中p0=p，pn=q，对每一个i，0i=n，当输入字符ai时，自动机能够从状态pi-1到达状态pi，即pid*(pi-1, ai)定义4.2a （NFA的d*函数的非递归定义）给定NFA M=（Q, , q0, d, A），p是任意一个状态，则d*(p, L)=p，对于任意一个字符串x= a1a2.an，d*(p, x)是所有满足下面条件的状态q组成的集合。存在一个状态路径p0, p1, ., pn，其中p0=p，pn=q，对每一个i，0i=n，序列b1, b2, ., bmL满足b1b2.bm=x，存在一组状态p=p0, p1, ., pm=q，对于每个1=i=0，L(p, q, j)表示所有从p到q，且经过状态的编号小于等于j的字符串组成的集合。由于M中状态的最大编号为n，显然L(p, q)中的字符串不会经过编号大于n的状态，因此L(p, q, n)=L(p, q)。现在问题变成证明L(p, q, n)是正则语言。我们可以用数学归纳法证明对任意的0=j=n，L(p, q, j)=L(p, q, n)=L(p, q)，我们要证明的命题可以更通用，即对任意的j=0，L(p, q, j)都是正则语言。1. 归纳基础，j=0，证明L(p, q, 0)是正则语言。既然M中状态的最小编号是1，L(p, q, 0)中的字符串表示的路径只能是从p直接到q，如果pq，则字符串是单个字母；如果p=q，还应包括空字符。空字符和单个字母都是正则语言，因此L(p, q, 0)是正则语言。2. 归纳推理，设对每个k=0，L(p, q, k)都是正则语言，证明L(p, q, k+1)也是正则语言。由于k=n时，L(p, q, k)= L(p, q, k+1)，此处仅证明kn的情况。L(p, q, k+1)的字符串表示的路径可分成两类，一种没有经过k+1号状态，即来自L(p, q, k)的元素；另一类经过了k+1号状态。只需证明第二类字符串组成的语言是正则语言。每个第二类字符串x可以分解成三部分yzw，y表示从p到k+1号状态的路径，z表示从k+1到k+1的路径，w表示从k+1到q的路径，因此yL(p, k+1, k)zL(k+1, k+1, k)*-此处有起点和终点相同，存在循环，即Kleene*运算wL(k+1, q, k)因此，第二类字符串组成的语言是，L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)，则L(p, q, k+1)= L(p, q, k)+ L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)根据正则语言的定义，正则语言的合并、连接和Kleene*运算后的结果仍然是正则语言。因此L(p, q, k+1)是正则语言，证明完毕。定理4.5的证明提供了一个从有限自动机（确定型非空转移的有限自动机）导出相应正则表达式的方法，总结如下：L(p, q, k+1)= L(p, q, k)+ L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)L(p, q)=L(p, q, n)L=例子4.10 图4-14给出了一个FA，求它对应的正则表达式。分析：我们用下表显示对应语言L(p, q, j)的正则表达式r(p, q, j)，0=j=2。pr(p, 1, 0)r(p, 2, 0)r(p, 3, 0)1a+Lbf2aLb3abLpr(p, 1, 1)r(p, 2, 1)r(p, 3, 1)1a*a*bf2a+L+a+bb3a+a*bLpr(p, 1, 2)r(p, 2, 2)r(p, 3, 2)1a*(ba+)*a*(ba+)*ba*(ba+)*bb2a+(ba+)*(a+b)*(a+b)*b3a+a*(ba+)+a*b(a+b)*L+a*b(a+b)*b上表在计算中，用到了一些简化方法，如：r(1, 3, 1)=r(1, 3, 0) + r(1, 1, 0)r(1, 1, 0)*r(1, 3, 0)= f其中r(1, 3, 0)=f，而空集与其他任何集合的连接运算结果仍是空集。r(3, 2, 1)= r(3, 2, 0)+r(3, 1, 0)r(1,1,0)*r(1,2,0)= b+a(a+L)*b= Lb+a+b= a*br(1,1,2) = r(1,1,1)+r(1,2,1)r(2,2,1)*r(2,1,1)= a* + a*b(a+b)*a+= a* + a*(ba+)*ba+= a* + a*(ba+)+= a*(ba+)*r(3,2,3) = r(3,2,1)+r(3,2,1)r(2,2,1)*r(2,2,1)= a*b + a*b(a+b)*(L+a+b)= a*b + a*b(a+b)*= a*b(a+b)*接受状态是1和2，因此要求的正则表达式r=r(1,1,3)+r(1,2,3)。r(1,1,3) = r(1,1,2)+r(1,3,2)r(3,3,2)*r(3,1,2)= a*(ba+)*+a*(ba+)*bb(L+a*b(a+b)*b)*(a+a*(ba+)+)= a*(ba+)*+a*(ba+)*bb(a*(ba+)*bb)*(a+a*(ba+)+)= a*(ba+)*+(a*(ba+)*bb)+(a+a*(ba+)+)r(1,2,3)= r(1,2,2)+r(1,3,2)r(3,3,2)*r(3,2,2)= a*(ba+)*b+a*(ba+)*bb(a*b(a+b)*b)*a*b(a+b)*= a*(ba+)*b+a*(ba+)*bb(a*(ba+)*bb)*a*b(a+b)*= a*(ba+)*b+(a*(ba+)*bb)+a*(ba+)*b= (a*(ba+)*bb)* a*(ba+)*br= r(1,1,3)+r(1,2,3)= a*(ba+)*+(a*(ba+)*bb)+(a+a*(ba+)+)+(a*(ba+)*bb)*a*(ba+)*b= a*(ba+)*+(a*(ba+)*bb)*(a*(ba+)*