05 正则语言的性质.ppt

1、1,形式语言与自动机,第5章 正则语言的性质,2,主要内容,正则语言(RL)的性质 泵引理及其应用 并、乘积、闭包、补、交 正则代换、同态、逆同态的封闭性 从正则语言固有特征寻求表示的一致性 Myhill-Nerode定理 FA的极小化 正则语言的几个判定问题 空否、有穷否、两个DFA等价否、成员关系,3,5.1 正则语言的泵引理,DFA在处理一个足够长的句子的过程中，必定会重复地经过某一个状态。 换句话说，在 DFA 的状态转移图中，必定存在一条含有回路的从启动状态到某个终止状态的路。 由于是回路，所以 DFA 可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可

2、以重复任意多次。,4,泵引理,5,泵引理,M = ( Q, , , q0 , F ) | Q |= N z = a1a2am , mN (q0 , a1a2ah) = qh 状态序列 q0, q1, ,qN 中，至少有两个状态是相同：qk=qj (q0 , a1a2ak) = qk (qk , ak+1aj) = qj = qk (qj , aj+1am) = qm 因此，可设 z = uvw，其中 u= a1a2ak，v=ak+1aj，w = aj+1am,6,泵引理,对于任意的整数 i 0 (qk , (ak+1aj)i ) =(qk , (ak+1aj)i-1 ) =(qk , ak+1

3、aj) = qk 故(q0 , a1a2ak (ak+1aj)i aj+1am) = qm 也就是说， a1a2ak (ak+1aj)i aj+1amL(M) 即 uviwL 。,7,泵引理 (pumping lemma),设 L 为一个 正则语言 ，则存在仅依赖于 L 的正整数 N， 对于 zL，如果 | z |N，则存在 u, v, w，满足 (1) z = uvw； (2) | uv | N； (3) | v | 1； (4) 对于任意的整数 i 0，uviw L； (5) N 不大于接受 L 的最小 DFA M 的状态数。,我们总能够在离 z 的开始处不太远的地方找到一个非空的 串 v

4、，然后可以把它看作一个“泵”，重复 v 任意多次， 或者去掉它，而所得到的结果串仍然属于L。,8,例5-1,证明 0n1n | n1 不是 RL。 证明：假设 L= 0n1n | n1是 RL。 不妨设 N 是泵引理所指的仅依赖于 L 的正整数，取 z = 0N1N ，则 z L。 按照泵引理所述，存在 u, v, w，使得 z=uvw。 由于 | uv | N，| v | 1，所以 v 只能由0组成， 可设 v=0k，k1 此时有，u = 0N-k-j , w=0j1N 从而有，uviw = 0N-k-j (0k)i 0j1N = 0N+(i-1)k1N 当 i =2 时，有： uv2w=0

5、N+(2-1)k1N = 0N+k1N 注意到 k1，所以，N+kN。 这就是说，0N+k1NL。 这与泵引理矛盾。所以，L不是 RL。,9,例5-2,证明 0n | n 为素数 不是 RL。 证明：假设 L= 0n | n为素数 是 RL。 取 z=0N+p L ，N+p 是素数。 不妨设 v=0k，k1 从而有 uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k 当 i=N+p+1时， N+p+(i-1)k = N+p+(N+p+1-1)k = N+p+(N+p)k = (N+p)(1+k) 注意到 k1，所以 N+p+(N+p+1-1)k=(N+p)(1+k) 不是素数。故

6、当 i=N+p+1时， uvN+p+1w=0(N+p)(1+k) L 这与泵引理矛盾。所以，L 不是 RL。,10,例5-3,证明 0n1m2n+m | m, n1 不是 RL。 证明：假设 L= 0n1m2n+m |m, n1 是 RL。 取 z=0N1N22N 设 v=0kk1 从而有 uviw = 0N-k-j(0k)i0j1N22N = 0N+(i-1)k1N22N uv0w = 0N+(0-1)k1N22N = 0N-k1N22N 注意到 k1， N-k+N=2N-k2N 0N-k1N22N L 这个结论与泵引理矛盾。所以，L 不是 RL。,11,泵引理的说明,用来证明一个语言不是

7、RL 不能用泵引理去证明一个语言是 RL。 (1) 由于泵引理给出的是 RL 的必要条件，所以，在用它证明一个语言不是 RL 时，我们使用反证法。 (2) 泵引理说的是对 RL 都成立的条件，而我们是要用它证明给定语言不是 RL ，这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号N 来表示这个“假定存在”、而实际并不存在的数。 (3) 由于泵引理指出，如果 L 是 RL ，则对任意的 zL，只要|z|N，一定会存在u, v, w，使 uviwL 对所有的 i 成立。因此，我们在选择 z 时，就需要注意到论证时的简洁和

8、方便。,12,泵引理的说明,(4) 当一个特意被选来用作“发现矛盾”的 z 确定以后，就必须依照 | uv | N 和 | v |1的要求，说明 v 不存在(对“存在u, v, w”的否定) 。 (5) 与选 z 时类似，在寻找 i 时，我们也仅需要找到一个表明矛盾的“具体”值就可以了(对“所有 i ”的否定)。 (6) 一般地，在证明一个语言不是 RL 的时候，我们并不使用泵引理的第(5)条。 (7) 事实上，引理所要求的 | uv | N 并不是必须的。这个限制为我们简化相应的证明提供了良好支撑扩充了的泵引理 。 (8) 如果希望证明一个语言是 RL，最直接的办法是给出该语言的正则文法描述

9、，或者是 FA, RE 描述。也可以直接使用一些已有的结果和RL的性质。,13,5.2 正则语言的封闭性,封闭性(closure property) 如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的 有效封闭性(valid closure property) 给定一个语言类的若干个语言的描述，如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的。 本节讨论 RL 的封闭性 RL 在哪些运算下是封闭的？,14,正则语言的封闭性,定理 5-1 RL 在并、乘积、闭包运算下是

10、封闭的。 根据 RE 的定义，立即可以得到此定理。 定理 5-2 RL 在补运算下是封闭的。 要点：原来接受的不接受，不接受的接受。 证明： M =( Q, , , q0 , F ) L(M)=L， 取 DFA M = ( Q, , , q0 , Q-F ) 显然，对于任意的 x*， (q0 , x)= f F (q0 , x)= f Q-F 即 xL(M) x L(M )， L(M )= *- L(M)。 所以， RL 在补运算下是封闭的。 定理得到证明。,15,RL的交,定理 5-3 RL 在交运算下封闭。 利用 M1M2 = (M1M2) 即可证明。 构造 M1 = (Q1, , 1 ,

11、 q1 , F1) 和 M2 = (Q2, , 2 , q2 , F2) 的交DFA。,M = (Q1Q2 , , , (q1 , q2) , F1F2) (p, q), a) = (1(p, a), 2(q, a) ),16,RL的交,pr,1,1,S,0,qs,qr,1,0,1,ps,0,0,17,正则语言的封闭性,定理：如果 L 和 M 是正则语言，则 L- M 也是正则语言。 证明：利用 L-M=L M。 定理：如果 L 是正则语言，则 LR = x | xR L 也是正则语言。 构造接受 LR 的有穷状态自动机： (1) 把 M 的状态转移图中的所有有向边的指向逆转。 (2) 令 M

12、 的初始状态为新的有穷自动机的唯一的接受状态。 (3) 增加一个状态 p0 为新的有穷自动机的初始状态，同时从该状态出发到 M 的所有接受状态都建立一个 转移。,18,问题,对字母表上的 RL L，令 DFA M = (Q, q , F ) 识别 L。 对于任意 (q, a)Q，设(q, a )=p，f (a) 是上的一个RL，假定 DFA Ma= ( Qa, ,a , q0a , Fa ) 识别 f (a)。 下面构造 FA MRS，主框架是 M，而它的“分支子模块”是Ma。 M 在状态 q 读入字符 a 时进入状态 p， 让 MRS 在状态 q 作空移动到 Ma 的开始状态 q0a， 并在

13、 Ma 中处理 f (a)，之后它一定处在 Ma 的某个终止状态。 从 Ma 的每一个终止状态到 M 的状态 p 引一条标记为的弧， 使 MRS回到状态 p。 如此下去，直到最后到达 M 的终止状态。 可见，RL 在这种运算下也是封闭的。 称这种运算为正则代换。,19,正则代换 (regular substitution),设,是两个字母表，映射,称为是从 到 的代换。 如果对于a，f (a)是上的 RL ，则称 f 为正则代换。,将 f 的定义域扩展到*上：,(1) f ()=； (2) f (xa)=f (x) f (a)。,将 f 的定义域扩展到,对于 L *,20,例5-4,设= 0,

14、 1 ，= a, b ，f (0)=a，f (1)=b*，则 f (010) = f (0) f (1) f (0) = ab*a f (11,00) = f (11)f (00) = f (1) f (1)f (0) f (0) = b*b*+aa = b*+aa,f (L(0*(0+1)1*) = L(a*(a+b*)(b*)*) = L(a*(a+b*)b*) = L(a*ab*+a*b*b*) = L(a*b*),21,正则代换,是正则代换, 则 (1) f ()=； (2) f ()=； (3) 对于 a，f (a) 是上的 RE； (4) 如果 r, s 是上的 RE，则 f (r

15、+s) = f (r)+f (s) f (rs) = f (r) f(s) f (r*) = f (r)* 是上的 RE。,设, 是两个字母表，映射,22,定理5-4,定理 5-4 设 L 是上的一个 RL，,是正则代换，则 f (L) 也是 RL。 证明思路：使用 RE 进行定理证明。 因为 L 是RL，则存在正则表达式 r，使得 L(r)=L。 对 r 中运算符的个数 n 施以归纳，证明 f (r)是表示 f (L)的 RE。 即证明：f ( L(r) ) = L( f(r) ) 当 n=0 时，结论成立。 当 nk 时定理成立，即当 r 中运算符的个数不大于 k 时： f ( L(r)

16、) = L( f (r) )。 当 n=k+1 时， 分 3 种情况： (1) r = r1+r2(2) r = r1r2(3) r = r1*,23,定理5-4,(1) r = r1+ r2。 f (L)= f ( L(r) ) = f ( L(r1+r2) ) = f ( L(r1)L(r2) )RE 的定义 = f ( L(r1) f (L(r2) )正则代换的定义 = L( f (r1)L (f (r2) )归纳假设 = L( f (r1)+f (r2)RE 的定义 = L( f (r1+r2) )RE 的正则代换的定义 = L( f (r) ),24,定理5-4,(2) r =r1r

17、2。 f (L)= f ( L(r) ) = f (L(r1r2) = f (L(r1) L(r2)RE 的定义 = f (L(r1) f (L(r2)正则代换的定义 = L(f (r1) L(f (r2)归纳假设 = L( f (r1) f (r2) )RE 的定义 = L( f (r1r2) )RE 的正则代换的定义 = L( f (r) ),25,定理5-4,(3) r=r1*。 f (L)= f ( L(r) ) = f ( L(r1*) ) = f (L(r1)*)RE 的定义 = ( f (L(r1) )*正则代换的定义 = ( L(f (r1) )*归纳假设 = L(f (r1)

18、*)RE 的定义 = L(f (r1*)RE 的正则代换的定义 = L( f (r) ),26,例5-5,设= 0, 1, 2 ，= a, b ，正则代换 f 定义为： f (0)=ab； f (1)=b*a*； f (2)=a*(a+b) 则： (1) f (00)=abab； (2) f (010)=abb*a*ab=ab+a+b； (3) f (0+1+2)*)=(ab+b*a*+ a*(a+b)* =(b*a*+a*(a+b)*=(a+b)*； (4) f (0(0+1+2)*)=ab(ab+b*a*+ a*(a+b)* =ab(a+b)*； (5) f (012)=abb*a*a*(

19、a+b)= ab+a*(a+b)； (6) f (0+1)*)= (ab+ b*a* )* = (ab+b+a+ b*a* )*=(a+b)* 。,27,同态映射 (homomorphism),设 , 是两个字母表，,f 为映射，如果对于 x, y*， f (xy) = f (x) f (y) 则称 f 为从 到 * 的同态映射。,28,同态映射,对于L*，L 的同态像,对于w *，w 的同态原像是一个集合,对于 L*，L 的同态原像是一个集合,29,例5-6,设= 0, 1 ，= a, b ，同态映射 f 定义为 f (0)=aa, f (1)=aba (1) f (01)= aaaba；

20、(2) f (01)*)= (aaaba)*； (3) f -1(aab)=； (4) f -1(aa)=0； (5) f -1( aaa, aba, abaaaaa, abaaaaaa) = 1, 100 ； (6) f -1(ab+ba)*a)=1； (7) f ( f -1(ab+ba)*a)=f (1)= aba 。 令 L=(ab+ba)*a，上述(7)表明，f ( f -1(L) ) L。 可以证明 f ( f -1(L) ) L,30,RL的同态像是RL,推论5-1 RL 的同态像是 RL。 注意到同态映射是正则代换的特例，可以直接得到此结论。 该定理表明， RL 在同态映射下是

21、封闭的。 定理 5-5 RL 的同态原像是 RL 。,31,RL 的同态原像是 RL,定理 5-5 RL 的同态原像是 RL 。 证明思路：使用 DFA 作为描述工具。 接受 RL 的同态原像的 FA 的构造思想。 让新构造出的 FA M 用一个移动去模拟 M 处理 f (a) 所用的一系列移动。 对于中的任意字符 a，如果 M 从状态 q 开始处理 f (a)，并且当它处理完 f (a) 时到达状态 p，则让 M 在状态 q 读入 a 时，将状态变成 p。 M 具有与 M 相同的状态，并且，在 M 对应的状态转移图中，从状态 q 到状态 p 有一条标记为 a 的弧当且仅当在M的状态转移图中，

22、有一条从状态 q 到状态 p 的标记为 f (a)的路。,32,RL 的同态原像是 RL,接受 RL 的同态原像的 FA 的形式描述。 设 DFA M=(Q, q0 , F )，L(M)=L， 取 DFA M =(Q, q0 , F ) (q, a)= ( q, f (a) ) 为了证明 L(M )=f -1(L(M) 只需证明，对于任意 x *， (q0 , x) F (q0 , f (x) F 为此，先证明 (q0 , x) =(q0 , f (x),33,RL 的同态原像是 RL,证明(q0 , x)=(q0 , f (x) 。 施归纳于 | x |。 当 | x | =0 时，结论显然

23、成立。 设当 | x |=k 是结论成立，往证当 | x |=k+1 时结论成立。 不妨设 x=ya，其中 | y |=k (q0 ,x)= (q0,ya) =( (q0 ,y), a) =(q0 ,f (y), a)归纳假设 =(q0 ,f (y), f (a) ) 的定义 =(q0,f (y) f (a) )的意义 =(q0,f (ya)同态映射性质 =(q0,f (x),34,RL 的同态原像是 RL,这表明，结论对 | x |=k+1 成立。 由归纳法原理，结论对 x* 成立。 现在证明：x*， (q0 , x)F (q0 , f(x) F。 由于对 x*， (q0 , x)=(q0

24、, f (x) )， 所以， (q0 , x)F (q0 , f (x)F。 故 L(M )=f -1( L(M) ) 定理得证。,35,商(quotient),设 L1 , L2 *， L1 除以 L2 的商定义为： L1/L2= x | yL2 使得 xyL1 计算语言的商主要是考虑语言句子的后缀。 只有当 L1 的句子的后缀在 L2 中时，其相应的前缀才属于 L1/L2。,36,商(quotient),考虑 0, 1 上的如下语言： (1) L1=(0+1)*，L2=0(0+1)*，则 L1/L2=L1 (2) L1=01，L2=01，则 L1/L2= L1=(01)*，L2=(01)*

25、，则 L1/L2=L1 (3) L1=0*011*，L2=00，则 L1/L2= (4) L1=(0+1)*0，L2=(0+1)*1，则 L1/L2= (5) L1=00*1*1，L2=00*1*1，则 L1/L2=0* (6) L1=00*1*1，L2=0*1*1，则 L1/L2=0*1* 注意：(L1/L2)L2=L1 和 L1/L2 L1 不一定成立。,37,商(quotient),注意以下有意思的情况： 取L1= 000 ，并分别除以 L2=, L3=,0, L4=,0,00 , L5=, 0, 00, 000 L1/L2= 000 = L1 L1/L3= 000, 00 L1/L4=

26、 000, 00, 0 L1/L5= 000, 00, 0, 注意：在充当“被除数”的集合不变的情况下，充当“除数”的集合越“大”，所得的“商”可能越大。,38,L1/L2 的封闭性,定理5-6 L1 , L2*，如果 L1 是 RL ，则 L1/L2 也是 RL 。 证明：设 L1 *， L1是 RL ， 则存在 DFA M1 =( Q, q0, F1)，使得 L(M1 )=L1 构造 DFA M2 = ( Q, q0 , F2 ) 其中 F2 = q | yL2 ,(q, y)F1 显然 L(M2 )= L1/L2。 定理得证。,39,5.3 Myhill-Nerode 定理与DFA的极小

27、化,对给定 RL L，DFA M 接受 L，M 不同，由 M 确定的*上的等价类也可能不同。 如果 M 是最小 DFA，则 M 所给出的等价类的个数应该是最少的。 最小 DFA 是不是惟一的？如果是，如何构造？ 最小 DFA 的状态对应的集合与其他 DFA 的状态对应的集合有什么样的关系，用这种关系是否能从一般的 DFA 出发，求出最小 DFA？,40,关系 RM,设 DFA M =( Q, , q0 , F )。 M 确定的*上的关系 RM 为： 对于 x , y* x RM y (q0 , x)=(q0 ,y)。 显然，x RM y qQ, x, yset(q) 因此，RM 决定了* 的一

28、个分类。,41,例5-8,设 L=0*10*，它对应的 DFA M 如右图所示。,对应于q0：(00)n RM (00)mn, m0； 对应于q1：0(00)n RM 0(00)mn, m 0； 对应于q2：(00)n1 RM (00)m1n, m 0； 对应于q3：0(00)n 1 RM 0(00)m1n, m 0； 对应于q4： 0(00)n 10k RM 0(00)m10hn, m 0, k, h 1； (00)n10k RM (00)m10hn, m 0, k, h 1； 0(00)n 10k RM (00)m10hn, m 0, k, h 1； 即： 0n 10k RM 0m10hn

29、, m 0, k, h1； 对应于q5：x RM yx, y 为至少含两个 1 的串。,42,关系 RL,L 确定的 *上的关系 RL。 对于 x, y*， x RL y ( 对z*，xzL yzL) 即：对于 x, y*，如果 x RL y，则在 x 和 y 后无论接*中的任何串 z，xz 和 yz 要么都是 L 的句子，要么都不是L 的句子。,43,关系 RM 与关系 RL,如果 L 是一个 RL，DFA M 接受的语言是 L，对于qQ，set(q)中的任意两个串x, y，必有 xRLy 成立，即xRL(M) y。 由于 x, yset(q)，所以(q0 , x)=(q0 , y)=q 对

30、于z*， (q0 , xz)=(q0 , x), z) =(q, z) =(q0 , y) , z) =(q0, yz) 这就是说，(q0 , xz)F (q0 , yz)F 即对于z*，xzL yzL。 表明，x RL y，也就是 x RL(M) y。,如果 xRM y，则必有 xRL(M) y。 如果 xRL(M) y，则不一定有 xRM y。,44,例,设 L=0*10*，它对应的 DFA M 如右图所示。,对应于q0：(00)n RM (00)mn, m0； 对应于q1：0(00)n RM 0(00)mn, m 0； 对应于q2：(00)n1 RM (00)m1n, m 0； 对应于q

31、3：0(00)n 1 RM 0(00)m1n, m 0； 对应于q4： 0n 10k RM 0m10hn, m 0, k, h1； 对应于q5：x RM yx, y 为至少含两个 1 的串。,00set(q0)， 0set(q1)， 0 RM 00不成立，但 0 RL(M) 00 成立。,45,右不变关系,右不变的 (right lnvariant) 等价关系 设 R 是*上的等价关系，对于 x, y*，如果 xRy，则必有 xz R yz 对于 z*成立，则称 R 是右不变的等价关系。,46,命题5-1,命题 5-1 对于任意 DFA M = ( Q, q0 , F )，M 所确定的*上的关

32、系 RM 为右不变的等价关系。 证明： (1) RM 是等价关系。 自反性： 因为( q0 , x ) =( q0 , x )，所以 x RM x 。 对称性：x, y*， x RM y ( q0 , x ) =( q0 , y )根据 RM 的定义； ( q0 , y ) =( q0 , x )“=”的对称性； y RM x根据 RM 的定义。,47,命题5-1,传递性：设 x RM y，y RM z。 由于 x RM y，(q0 ,x) =(q0 ,y) 由于 y RM z，(q0 ,y) =(q0 , z) 由 “=” 的传递性知， (q0 ,x) =(q0 ,z) 再由 RM 的定义得

33、： x RM z 综上，RM 是等价关系。,48,命题5-1,(2) RM是右不变的 设 x RM y，则(q0 , x)=(q0 , y)=q 所以，对于z*， (q0 , xz)=(q0 , x), z) =(q, z) =(q0 , y), z) =(q0 , yz) 由 RM 的定义， xz RM yz 所以， RM 是右不变的等价关系。,49,命题5-2,命题 5-2 对于任意 L *，L 所确定的*上的关系 RL 为右不变的等价关系 。 证明： (1) RL是等价关系。 自反性显然。 对称性：不难看出： x RL y (对 z*，xzL yzL ) y RL x 传递性：设 x R

34、L y，y RL z。 x RL y ( 对 w*，xwL ywL ) y RL z ( 对 w*，ywL zwL ) 所以，(w*,xwL ywL 且 ywL zwL ) 即：(对w*，xwL zwL) 故：x RL z 即 RL 是等价关系。,50,命题5-2,(2) RL 是右不变的。 设 x RL y。由 RL 的定义，对 w, v*， xwvL zwvL，注意到 v 的任意性，知 xw RL yw。 所以， RL 是右不变的等价关系。,51,指数(index),设 R 是*上的等价关系，则称 |*/R| 是 R 关于*的指数。简称为 R 的指数。 * 的关于R 的一个等价类，也就是*

35、/R 的任意一个元素，简称为 R 的一个等价类 。,52,例5-9,右图所给 DFA M 所确定的 RM 的指数为 6。 RM 将*分成 6 个等价类： set(q0)= (00)n | n0 ； set(q1)= 0(00)n | n0 ； set(q2)= (00)n1 | n, m0 ； set(q3)= 0(00)n 1| n0 ； set(q4)= 0n10k | n0, k1 ； set(q5)= x | x 为至少含两个 1 的串。,53,RM 与 RL(M),x, y*，如果 x RM y，必有 xRL(M) y 成立。 对于任意 DFA M=(Q, q0, F)： (1) |

36、*/ RL(M) |*/RM|Q| (2) 按照 RM 中被分在同一等价类的串，在按照 RL(M) 分类时，一定会被分在同一个等价类。 RM对 * 的划分比 RL(M) 对 * 的划分更“细”。 称 RM 是 RL(M) 的“加细”(refinement)。,54,问题讨论,在*/RM = set(q0), set(q1), set(q2), set(q3), set(q4), set(q5) 中， 是否存在有根据 RL(M) 可以“合并” 的等价类？ (1) 取 00set(q0)，000set(q1)。 对于任意的 x*， 当 x 含且只含一个 1 时，00 xL(M)，000 xL(M)

37、； 当 x 不含 1 或者含多个 1 时，00 xL(M)，000 xL(M)。 这就是说，对于任意 x*，00 xL(M) 000 xL(M)。即按照 RL(M)，00 与 000 被分在同一个等价类中。 从而 set(q0) 和 set(q1) 被包含在 RL(M) 的同一个等价类中。,55,问题讨论,(2) 取 00set(q0)，001set(q2)。 取特殊的字符串1*，001L(M)，但0011L(M)。所以，根据 RL(M)，set(q0) 和 set(q2)不能被“合并”到一个等价类中。 类似地，根据 RL(M)，set(q3)、set(q4)、set(q5) 也都不能被“合并

38、”到 set(q0) 的句子所在的等价类中。 (3) 取 001set(q2)，01set(q3)。 对于任意的 x*，x 要么不含 1，要么含有 1。 当 x 不含 1 时，001xL(M)，01xL(M)； 当 x 含有 1 时，001xL(M)，01xL(M)。 这就是说，对于任意 x*，001xL(M) 01xL(M)。即按照 RL(M)，001 与 01 属于 RL(M) 的同一个等价类中。从而set(q2) 和 set(q3) 被包含在 RL(M) 的同一个等价类中。,56,问题讨论,(4) 取 1set(q2)， 10set(q4)。 对于任意的 x*，x 要么不含 1，要么含有

39、 1。 当 x 不含 1 时，1xL(M)，10 xL(M)； 当 x 含有 1 时，1xL(M)，10 xL(M)。 这就是说，对于任意的 x*，1xL(M) 10 xL(M)。即按照 RL(M)，1 与 10 被分在 RL(M) 的同一个等价类中。 从而在 set(q2) 和 set(q4) 被包含在 RL(M) 的同一个等价类中。 (5)取 1set(q2)， 11set(q5)。 注意到 1=1，11=11；而1L(M)，11L(M)。即 1 和 11不满足关系 RL(M)，所以，set(q2) 和 set(q5) 不能被“合并”到RL(M) 的同一个等价类中。在这里，* 是一个特殊的

40、字符串。,57,问题讨论,*/RL(M)= set(q0)set(q1)，set(q2)set(q3)set(q4)，set(q5) 不含 1： 0= set(q0)set(q1) = 0*； 含一个 1： 1= set(q2)set(q3)set(q4) = 0*10*； 含多个 1： 11= set(q5) = 0*10*1(0+1)* 。,58,Myhill-Nerode 定理,米希尔-尼德罗定理 如下三个命题等价： (1) L *是 RL 。 (2) L 是 * 上的某一个具有有穷指数的右不变等价关系 R 的某些等价类的并。 (3) RL 具有有穷指数。,59,由(1)可以推出(2),

41、(1) L *是 RL 。 (2) L 是 * 上的某一个具有有穷指数的右不变等价关系 R 的某些等价类的并。 设 L *是 RL ， 所以，存在 DFA M = ( Q, q0, F )，使得 L(M)=L。 由命题5-1，RM 是 * 上的右不变等价关系， 而且 |*/RM | Q |，所以，RM 具有有穷指数。而,即 L 是 * 上的具有有穷指数的右不变等价关系 RM 的、对应于 M 的终止状态的等价类的并。,60,由(2)可以推出(3),(2) L 是 * 上的某一个具有有穷指数的右不变等价关系 R 的某些等价类的并。 (3) RL 具有有穷指数。 设 xRy，由 R 的右不变性可知，

42、对于任意 z*， xzRyz 而 L 是 R 的某些等价类的并，所以 xzL yzL 根据 RL 的定义， xRL y 故 R 是 RL 的加细。 由于 R 具有有穷指数，所以，RL 具有有穷指数。,61,由(3)可以推出(1),(3) RL 具有有穷指数。 (1) L * 是 RL 。 设 RL 具有有穷指数。往证存在 DFA M ，使得 L(M )=L。 思路是用等价类对应状态，状态之间的转移依据相应的等价类的变化。 令 M =(*/RL, , , , x | xL ) 表示所在的等价类对应的状态； x 表示 x 所在的等价类对应的状态。 对于 (x, a)(*/RL), (x, a) =

43、 xa 定义具有相容性 (如果x=y，那么 xa=ya) 如果 x 和 y 同处一个等价类，即 x=y，有 xRLy， 由 RL 的右不变性，有 xaRLya 即 xa=ya。 因此，L(M )=L。,62,例5-10,用定理5-7证明 0n1n | n0 不是 RL。 思路：根据 L 的句子的特征来寻找 RL 的等价类。 L 的句子的主要特点有两个： (1) 句子中所含的字符 0 的个数与所含的字符 1 的个数相同。 (2) 所有的 0 都在所有的 1 的前面。 由此可知，对所有的串 x，如果 x 是 0n1m ( mn+1)，或者 x 中含有子串10，则无论 x 后面接任何串 z，都有 x

44、z 不属于L。 将此等价类记为 10。 再考虑形如 0n 形如 0n1m 的串， m, n0 且 n m。 注意到 01L，001L，所以 0 和 00 不在同一个等价类中。 可以得到如下一些等价类。,63,例5-10,10= x | x=0n1m (mn+1) 或者 x 中含子串 10 所在的等价类； 10 所在的等价类； 200 所在的等价类； 3000 所在的等价类； n0n 所在的等价类； 所以，RL 的指数是无穷的。因此，L 不是 RL。,64,Myhill-Nerode 定理的推论,推论 5-2 对于任意的 RL L，如果 DFA M=(Q, q0 , F) 满足 L(M)=L，则

45、|*/RL|Q|。 即 对于任意DFA M=(Q, q0, F)，|Q|*/RL(M)|。 也表明，对任意一个 RL L，按照定理5-7中所给的方法构造出来的DFA M 是一个接受 L 的最小DFA。 问题：这个 DFA 是惟一的么？ 推论5-3 对于任意的 RL L，在同构意义下，接受 L 的最小DFA是惟一的。 接受 L 的最小 DFA M=(Q, , q0 , F) 定理5-7 构造的 DFA M =(*/RL, , , , x | xL ) M 与 M 同构，是指二者的状态数一一对应，状态转移也是一一对应的。 定义映射：f (q)=f (q0 , x) )= ( , x )=x 即让

46、M 的状态 x 与 M 的状态 q=(q0 , x) 对应， 该状态正是 x 引导 M 从 q0 出发所到达的状态。,65,推论5-3,推论5-3 对于任意的 RL L，在同构意义下，接受 L 的最小DFA 是惟一的。 证明： 接受 L 的最小 DFA M = (Q, q0 , F) 的状态数与 RL 的指数相同，也就是说，这个最小 DFA 的状态数与 Myhill-Nerode 定理证明中构造的 M =(*/RL, , , x | xL )的状态数是相同的。 DFA 同构是指这两个 DFA 的状态之间有一个一一对应，而且这个一一对应还保持状态转移也是相应一一对应的。也就是说，如果 q 与 w

47、 对应，p 与 z 对应，当(q, a)=p时，必定有(w, a)=z。 这两个 DFA 是同构。定义映射 f f (q)=f (q0 , x) )= ( , x)=x 即让 M 的状态 x 与 M 的状态 q=(q0 , x)对应， 该状态正是 x 引导 M 从 q0 出发所到达的状态。,66,推论5-3,往证 f 为 Q 与 */RL 之间的一一对应。 如果(q0 ,x)=(q0 ,y)，则 xRM y 由于 RM 是 RL 的加细，所以，x RL y 故，x=y，即(, x)=(, y)。 如果(q0 ,x)(q0 ,y) 则 (，x) (, y) 即xy 否则|*/RM |*/RL |

48、。 这与 M 是最小 DFA 矛盾。 所以，f 是 Q 与 */RL 之间的一一对应。,67,推论5-3,往证，如果(q, a)=p，f (q)=f (q0,x)=x， 由于 (, xa)=xa，因此必有 f (p)=xa。 事实上，对于 qQ， 如果f (q) = f (q0,x)=x 则对于 a，如果 p=(q, a)=(q0,x), a)=(q0,xa ) 则 f (p)=f (q, a)= f (q0 ,x), a)=f (q0 ,xa)=xa 即如果 M 在状态 q 读入字符 a 时进入状态 p， 则 M 在 q 对应的状态 f (q0 ,x)=x 读入字符 a 时，进入 p 对应的

49、状态 f (q0 ,xa) )=xa。 所以，f 是 M 和 M 之间的同构映射。,68,DFA的极小化,对于任给的 RL L，接受 L 的最小 DFA 是唯一的。 按照 L 所决定的等价关系 RL 的等价类来设立状态和状态之间的转移函数是构造最小 DFA 的一种方法。 计算机求解困难 对于 RL L，如果有一个 DFA M，使得 L(M)=L，可以通过合并 RM 的等价类来求出 RL 的等价类。注意这些等价类对应的是状态。 做法：分别从 set(q) 和 set(p) 中各取一个利于考察的“适当”字符串 x, y，然后研究对于任意的 z，xz 和 yz 同时属于L 或者同时不属于 L。 具有

50、较高的复杂性,69,DFA的极小化,考虑哪些状态不可以合并。 (1)Q-F 中的任意状态和 F 中的任意状态是不能合并的。 设 qQ-F，pF，xset(q)，yset(p)， 则有 x不属于 L，而 y属于 L，x 和 y 不满足关系 RL， 所以 q 和 p 不能合并。 由此得到第一批不能合并的状态对。 (2) 考察其它不知能否合并的状态对 q 和 p 。 如果 中存在字符 a，使得(q, a)=q，(p, a)=p， 则 q 和 p 也是不能合并的。 当找出所有的不可以合并的状态对后，剩余的状态对就是可以合并的了。,70,可区分状态,可以区分的 (distinguishable) 状态

51、设 DFA M = ( Q, q0 , F )，如果 x*， 对 Q 中的两个状态 q 和 p，使得 (q, x)F 和(p, x)F 中，有且仅有一个成立，则称 p 和 q 是可以区分的。 否则，称 q 和 p 等价。并记作 qp 。,71,DFA的极小化算法,算法5-1 DFA 的极小化算法 算法思想：扫描所有的状态对，找出所有的可区分的状态对，不可区分的状态对一定是等价的。 输入：给定的 DFA。 输出：可区分状态表。 主要数据结构：状态对的关联链表，可区分状态表。,72,DFA的极小化算法,主要步骤 (1) for (q, p)F(Q-F) do 标记可区分状态表中的表项 (q, p)

52、；/ p 和 q 不可合并 (2) for (q, p)FF(Q-F) (Q-F) & qp do (3) if a，可区分状态表中的表项(q,a),(p,a)已被标记 then begin (4) 标记可区分状态表中的表项(q, p)； (5) 递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项 end (6) else for a，do (7) if (q,a)(p,a) &(q,p)与(q,a),(p,a)不是同一个状态对 then 将(q,p)放在(q,a),(p,a)的关联链表上。,73,定理5-8,定理5-8 对于任意DFA M=(Q,q0 , F)，Q

53、中的两个状态q和p是可区分的充要条件是(q,p)在DFA的极小化算法中被标记。 必要性的证明。 设q和p是可区分的，x是区分q和p的最短字符串。现施归纳于x的长度，证明(q，p)一定被算法标记。 当|x|=0时 区分q和p，表明q和p有且仅有一个为M的终止状态，所以，(q,p)F(Q-F) 因此，它在算法的第(1)行被标记。 设当|x|=n时结论成立 x是区分q和p的长度为n的字符串，则(q,p)被算法标记。,74,定理5-8,当|x|=n+1时 设x=ay，其中|y|=n。由于x是区分q和p的最短的字符串，所以，(q,x)F 和(p,x)F中，有且仅有一个成立。 不妨假设：(q,x)F ，(

54、p,x)F 即(q,a)，y)F ，(p,a),y)F 设(q,a)=u，(p,a)=v y是区分u和v的长度为n的字符串。 由归纳假设，(u,v)可以被算法标记。 如果在考察(q,p)时，(u,v)已经被标记，则(q,p)在算法的第(4)行被标记； 如果在考察(q,p)时，(u,v)还没有被标记，则(q,p)在算法的第(7)行被放入到(u,v)的关联链表中，而当(u,v)被标记时，在算法的第(5)行在“递归”过程中(q,p)被标记。 结论对|x|=n+1成立。,75,定理5-8,充分性的证明。 设(q,p)在算法中被标记。对它被标记的顺序n施归纳，证明q和p是可区分的。 令|F(Q-F)|=

55、m，显然，当1nm时，(q,p)是在算法的第(1)行被标记的，此时，是区分q和p的字符串： (q,)F 和(p,)F 有且仅有一个成立。 设nk(km)时结论成立。即，如果 (q,p)是被算法在第k个或者第k个之前标记的，则存在字符串x，x区分q和p。即：(q,x)F 和(p,x)F有且仅有一个成立。,76,定理5-8,当n=k+1时，如果(q,p)是在算法的第(4)行被标记的，此时，(q,a),(p,a)一定是在第k个之前被标记的。设(q,a)=u，(p,a)=v，由归纳假设，存在字符串x，x区分u和v： (u,x)F 和(v,x)F 有且仅有一个成立，从而， (q,ax)F 和(p,ax)

56、F 有且仅有一个成立。即，ax是区分q和p的字符串。 如果(q,p)是在算法的第(5)行被标记的，则它必在某个状态对(u,v)的关联链表中，而(u,v)必在(q,p)之前被标记。由归纳假设，存在x区分(u，v)； 存在a，(q,a)=u，(p,a)=v使得(q,p)被放在(u,v)的关联链表中；ax是区分q和p的字符串。 所以，结论对n=k+1成立。由归纳法原理，结论对所有的n成立。,77,定理5-9,定理5-9 由算法5-1构造的DFA在去掉不可达状态是最小DFA 。 证明： 设M=(Q,q0,F)为算法5-1的输入DFA， M =(Q/, , q0,F )是相应的输出DFA。 F =q|q

57、F。 对于 qQ/， a，定义 (q,a)=(q,a),78,定理5-9, 的相容性。 设q=p ，也就是说，q和p等价：qp。即根据算法5-1，状态q和p是不可区分的(未被算法标记)。此时，对于 a，必须有(q,a)(p,a)。否则，状态对(q,a)，(p,a)必定被算法标记，从而最终导致(q，p)被算法标记。此与qp矛盾。所以，状态(q,a)和状态(p,a) 等价：(q,a)=(p,a)。所以， 的定义是相容的。,79,定理5-9,L(M )=L(M) 。 对x*，现施归纳于|x|，证明 (q0,x)=(q0,x) |x|=0 (q0,)=q0=(q0 ,) x*并且|x|=n， (q0，

58、xa)=(q0,x),a) =(q0 ,x),a) =(q0 ,x),a) =(q0 ,xa) 由归纳法原理，结论对x*成立。,80,定理5-9,再由F 的定义， (q0,x)=(q0 ,x)F (q0,x)F。 所以， xL(M) xL(M)。 即： L(M )=L(M)。,81,定理5-9,证明所构造的M 去掉不可达状态后是最小DFA。 如果qp，则对于xset(q)，yset(p)，x RL y不成立。事实上，如果qp，则存在z*，z区分q和p，有(q,z)=q 和(p,z)= p 有且仅有一个是终止状态，这就是说，xz和yz有且仅有一个是L的句子。所以，x RL y是不成立的。,82,例5-11,用算法 5-1 对下图所给的 DFA 进行极小化。,83,例5-12,用算法 5-1 对下图所给的 DFA 进行极小化。,84,例5-12,85,5.4 关于正则语言的判定算法,正则语言的表示