形式语言与自动机理论--第五章 正则语言的性质1（第十一周）

1、第第5章章 正则语言的性质正则语言的性质 1.1.正则语言的泵引理正则语言的泵引理2.2.正则语言的封闭性正则语言的封闭性3.Myhill-Nerode3.Myhill-Nerode定理与定理与DFADFA的极小化的极小化4.4.正则语言的判定算法正则语言的判定算法5.5.小节小节11. 正则语言的泵引理正则语言的泵引理 DFA是是RL的识别器。的识别器。DFA中状态个数是有穷的。中状态个数是有穷的。DFA在处理一个足够长的句子的过程中，必定会重复在处理一个足够长的句子的过程中，必定会重复地经过某一个状态。地经过某一个状态。换句话说，在换句话说，在DFA的状态转移图中，必定存在一条含的状态转移

2、图中，必定存在一条含有回路的从启动状态到某个终止状态的路。由于是回路，有回路的从启动状态到某个终止状态的路。由于是回路，所以，所以，DFA可以根据实际需要沿着这个回路循环运行，可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可以重复相当于这个回路中弧上的标记构成的非空子串可以重复任意多次。任意多次。 2例如：识别语言00110010101在识别过程中经过状态依次为：qs,q0,q0,q1,q0,q0,q0,q1,q2,q2,q1,q031.正则语言的泵引理正则语言的泵引理41.正则语言的泵引理正则语言的泵引理 下面给出判定一个语言不是下面给出判定一个语言不是RL的

3、一般方法的一般方法设设L是是RL，对应的，对应的DFA定义如下：定义如下： M=(Q，q0，F) |Q|=N 假设自动机有假设自动机有N个状态个状态 z= a1a2ammN (q0，a1a2ah)=qh 状态序列状态序列q0，q1，qN中，至少有两个状态是相同：中，至少有两个状态是相同：qk=qj 51.正则语言的泵引理正则语言的泵引理 (q0，a1a2ak)=qk(qk，ak+1aj)=qj=qk(qj，aj+1am)=qm 其中其中qm 为终止状态为终止状态所以，对于任意的整数所以，对于任意的整数i0 (qk，(ak+1aj)i)=(qk，(ak+1aj)i-1)=(qk，ak+1aj)=

4、qk 61.正则语言的泵引理正则语言的泵引理 故，故，(q0，a1a2ak(ak+1aj)i aj+1am)=qm也就是说，也就是说， a1a2ak(ak+1aj)i aj+1amL(M) u= a1a2ak，v=ak+1aj，w= aj+1am uviwL 由于由于kN,kN。这就是说，这就是说，0N+k1N L这与泵引理矛盾。所以，这与泵引理矛盾。所以，L不是不是 RL。 111.正则语言的泵引理正则语言的泵引理 例例 5-2 证明证明0n|n为素数为素数不是不是 RL。 证明：假设证明：假设L=0n|n为素数为素数 是是 RL。 取取 z=0N+p L ，其中，其中N+p是素数是素数不妨

5、设不妨设v=0k，k1 从而有，从而有，uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k121.正则语言的泵引理正则语言的泵引理 当当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)不是素数。故当不是素数。故当i=N+p+1时，时，uvN+p+1w=0(N+p)(1+k) L这与泵引理矛盾。所以，这与泵引理矛盾。所以，L不是不是 RL。 131.正则语言的泵引理正则语言的泵引理例例 5-3 证明证明0n1m2n+m|m，n1不

6、是不是 RL。 证明：假设证明：假设L=0n1m2n+m|m，n1 是是 RL。 取取z=0N1N22N 设设 v=0k k1 从而有，从而有，uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22N141.正则语言的泵引理正则语言的泵引理uv0w=0N+(0-1)k1N22N= 0N-k1N22N 注意到注意到k1，N-k+N=2N-k2N0N-k1N22N L这个结论与泵引理矛盾。所以，这个结论与泵引理矛盾。所以，L不是不是 RL。 151.正则语言的泵引理正则语言的泵引理用来证明一个语言不是用来证明一个语言不是 RL不能用泵引理去证明一个语言是不能用泵引理去证明一个语

7、言是 RL。 由于泵引理给出的是由于泵引理给出的是 RL 的必要条件，所以，的必要条件，所以，在用它证明一个语言不是在用它证明一个语言不是 RL 时，我们使用反证法。时，我们使用反证法。 泵引理说的是对泵引理说的是对 RL 都成立的条件，而我们都成立的条件，而我们是要用它证明给定语言不是是要用它证明给定语言不是 RL ，这就是说，相应，这就是说，相应语言的语言的“仅仅依赖于仅仅依赖于L的正整数的正整数N”实际上是不存在实际上是不存在的。所以，我们一定是无法给出一个具体的数的。的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号因此，人们往往就用符号N来表示这个来表示这个“假定存假

8、定存在在”、而实际并不存在的数。、而实际并不存在的数。 161.正则语言的泵引理正则语言的泵引理 由于泵引理指出，如果由于泵引理指出，如果L是是 RL ，则对任意的，则对任意的zL，只要，只要|z|N，一定会存在，一定会存在u、v、w，使，使uviwL对所有的对所有的i成立。因此，我们在选择成立。因此，我们在选择z时，就需要注意时，就需要注意到论证时的简洁和方便。到论证时的简洁和方便。 当一个特意被选来用作当一个特意被选来用作“发现矛盾发现矛盾”的的z确定确定以后，就必须依照以后，就必须依照|uv|N和和|v|1的要求，说明的要求，说明v不存不存在在(对对“存在存在u、v、w”的否定的否定)

9、。171.正则语言的泵引理正则语言的泵引理 与选与选z时类似，在寻找时类似，在寻找i时，我们也仅需要找到一时，我们也仅需要找到一个表明矛盾的个表明矛盾的“具体具体”值就可以了值就可以了(对对“所有所有i”的的否定否定)。 一般地，在证明一个语言不是一般地，在证明一个语言不是 RL 的时候，我们的时候，我们并不使用泵引理的第并不使用泵引理的第(5)条。条。 事实上，引理所要求的事实上，引理所要求的|uv|N并不是必须的。这并不是必须的。这个限制为我们简化相应的证明提供了良好支撑个限制为我们简化相应的证明提供了良好支撑扩充了的泵引理扩充了的泵引理 。182.正则语言的封闭性正则语言的封闭性 定义定

10、义5-1：封闭性：封闭性(closure property) 如果任意的、属于同一语言类的语言在某一特如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语定运算下所得的结果仍然是该类语言，则称该语言类对此运算是言类对此运算是封闭封闭的的有效封闭性有效封闭性(valid closure property)给定一个语言类的若干个语言的描述，如果存给定一个语言类的若干个语言的描述，如果存在一个算法，它可以构造出这些语言在给定运算在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的

11、运算是称此语言类对相应的运算是有效封闭有效封闭的。的。192.正则语言的封闭性正则语言的封闭性 定理定理 5-1 RL 在并、乘积、闭包运算下是在并、乘积、闭包运算下是封闭封闭的。的。根据根据RE的定义，立即可以得到此定理。的定义，立即可以得到此定理。202.正则语言的封闭性正则语言的封闭性 定理定理 5-2 RL 在补运算下是封闭的。在补运算下是封闭的。 证明证明： M=(Q，q0，F) L(M)=L， 取取DFA M= (Q，q0，Q-F) 显然，对于任意的显然，对于任意的x*， (q0，x)=fF (q0，x)=f Q-F 即：即： xL(M) x L(M)， L(M)= *-L(M)。

12、 所以，所以， RL 在补运算下是封闭的。定理得到证在补运算下是封闭的。定理得到证明。明。 212.正则语言的封闭性正则语言的封闭性 定理定理 5-3 RL 在交运算下封闭。在交运算下封闭。证明证明思路思路222.正则语言的封闭性正则语言的封闭性 2.正则语言的封闭性正则语言的封闭性 2.正则语言的封闭性正则语言的封闭性 2.正则语言的封闭性正则语言的封闭性 2. 正则语言的封闭性正则语言的封闭性 定义定义5-2：正则代换：正则代换(regular substitution) 设设、是两个字母表，映射是两个字母表，映射 *2:f被称为是从被称为是从到到的的代换代换。如果对于。如果对于 a，f(

13、a)是是上的上的 RL RL ，则称，则称f f为为正则代换。正则代换。 272. 正则语言的封闭性正则语言的封闭性 先将先将f的定义域扩展到的定义域扩展到*上：上： *2:*f f()= f()=； f(xa)=f(x)f(a)f(xa)=f(x)f(a)。282. 正则语言的封闭性正则语言的封闭性 再将再将f的定义域扩展到的定义域扩展到*2*22:f对于对于 L * LxxfLf)()(292. 正则语言的封闭性正则语言的封闭性 例例 5-4 设设=0，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)

14、 =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*) 302. 正则语言的封闭性正则语言的封闭性 定义定义5-35-3：f f是正则代换是正则代换, ,则则 f()=； f()=； 对于对于 a，f(a)是是上的上的RERE； 如果如果r，s是是上的上的RERE，则，则 f(r+s)=f(r)+f(s) f(rs)=f(r)f(s) f(r*)=f(r)* 是是上的上的RERE。 312. 正则语言的封闭性正则语言的封闭性 定理定理 5-4

15、 设设L是是上的一个上的一个 RL *2:f证明：证明：描述工具：描述工具：RE。对对r中运算符的个数中运算符的个数n施以归纳，证明施以归纳，证明f(r)是表示是表示f(L)的的RE。 322. 正则语言的封闭性正则语言的封闭性 当当n=0时时，结论成立。，结论成立。当当nk时定理成立时定理成立, ,即当即当r r中运算符的个数不大于中运算符的个数不大于k k时：时：f(L(r) = L(ff(L(r) = L(f(r)）。 当当n=k+1时，时，332. 正则语言的封闭性正则语言的封闭性 r=r1+r2。 f(L)=f(L(r) =f(L(r1+r2) =f(L(r1)L(r2) RERE的

16、定义的定义 =f(L(r1)f(L(r2) 正则代换的定义正则代换的定义 =L(f(r1)L (f (r2) 归纳假设归纳假设 =L(f(r1)+f (r2) RERE的定义的定义 =L(f(r1+r2) RERE的正则代换的定义的正则代换的定义 =L(f(r)342. 正则语言的封闭性正则语言的封闭性 r=r1r2。 f(L)=f(L(r) =f(L(r1r2) =f(L(r1) L(r2) RERE的定义的定义 =f(L(r1) f(L(r2) 正则代换的定义正则代换的定义 =L(f(r1) L (f (r2) 归纳假设归纳假设 =L(f(r1) f (r2) RERE的定义的定义 =L(

17、f(r1r2) RERE的正则代换的定义的正则代换的定义 =L(f(r)352. 正则语言的封闭性正则语言的封闭性 r=r1*。 f(L)=f(L(r) =f(L(r1*) =f(L(r1)*)RERE的定义的定义 =(f(L(r1)*正则代换的定义正则代换的定义 =(L(f(r1)*归纳假设归纳假设 =L(f(r1)*)RERE的定义的定义 =L(f(r1*)RERE的正则代换的定义的正则代换的定义 =L(f(r)362. 正则语言的封闭性正则语言的封闭性 例例5-5 设设=0，1，2，=a=a，bb，正则代换，正则代换f f定定义为：义为： f(0)=ab； f(1)=b*a*； f(2)

18、=a*(a+b)则：则： f(00)=abab； f(010)=abb*a*ab=ab+a+b； 372. 正则语言的封闭性正则语言的封闭性 f(0+1+2)*)=(ab+b*a*+ a*(a+b)*=(b*a*+a*(a+b)*=(a+b)*； f(0(0+1+2)*)=ab(ab+b*a*+ a*(a+b)* =ab(a+b)*； f(012)=abb*a* a* (a+b)= ab+a*(a+b)； f(0+1)*)=(ab+ b*a* )*=(ab+b+a+ b*a* )*=(a+b)* 。382. 正则语言的封闭性正则语言的封闭性 定义定义5-4：同态映射：同态映射(homomorp

19、hism) 设设、是两个字母表，是两个字母表，*:ff f为映射，如果对于为映射，如果对于 x，y*，f(xy)=f(x)f(y)，则称则称f为从为从到到*的的同态映射。同态映射。392. 正则语言的封闭性正则语言的封闭性 对于对于 L *，L的同态像的同态像 LxxfLf)()(对于对于 w *，w的同态原像是一个集合的同态原像是一个集合 &)(|)(*1xwxfxwf对于对于 L *，L的同态原像是一个集合的同态原像是一个集合 )(|)(1LxfxLf402. 正则语言的封闭性正则语言的封闭性 例例5-6 设设=0，1，=a=a，bb，同态映射，同态映射f f定义定义为为 f(0)=aa

20、f(1)=aba则：则： f(01)=aaaba； f(01)*)=(aaaba)*； f -1(aab)=； 412. 正则语言的封闭性正则语言的封闭性 f -1(aa)=0； f -1(aaa，aba，abaaaaa，abaaaaaa)=1，100； f -1(ab+ba)*a)=1； f(f -1(ab+ba)*a)=f(1)=aba。 令令L=(ab+ba)*a，上述，上述(7)表明，表明，f(f -1(L) L f(f -1(L) L 422. 正则语言的封闭性正则语言的封闭性 推论推论5-1 RL 的同态像是的同态像是 RL。证明：证明：注意到同态映射是正则代换的特例，可以直接得到

21、注意到同态映射是正则代换的特例，可以直接得到此结论。此结论。该定理表明，该定理表明， RL 在同态映射下是封闭的。在同态映射下是封闭的。 432. 正则语言的封闭性正则语言的封闭性 定理定理 5-5 RL 的同态原像是的同态原像是 RL 。证明：证明：使用使用DFA作为描述工具。作为描述工具。(1) 接受接受RL的同态原像的的同态原像的FA的构造思想。的构造思想。 让新构造出的让新构造出的FA M用一个移动去模拟用一个移动去模拟M处理处理f(a)所用的一系列移动。所用的一系列移动。对于对于中的任意字符中的任意字符a，如果，如果M从状态从状态q开始处开始处理理f(a)，并且当它处理完，并且当它处

22、理完f(a)时到达状态时到达状态p，则让，则让M在状态在状态q读入读入a时，将状态变成时，将状态变成p。442. 正则语言的封闭性正则语言的封闭性 M具有与具有与M相同的状态，并且，在相同的状态，并且，在M对应的状态转对应的状态转移图中，从状态移图中，从状态q到状态到状态p有一条标记为有一条标记为a的弧当且仅当在的弧当且仅当在M的状态转移图中，有一条从状态的状态转移图中，有一条从状态q到状态到状态p的标记为的标记为f(a)的路。的路。(2) 接受接受RL的同态原像的的同态原像的FA的形式描述。的形式描述。 设设DFA M=(Q，q0，F)，L(M)=L，取取DFA M=(Q，q0，F) (q，

23、a)= (q，f(a) 452. 正则语言的封闭性正则语言的封闭性 (3) 等价证明。等价证明。 施归纳于施归纳于|x|，证明对于，证明对于 x*，(q0，x)=(q0，f(x)当当|x|=0时，结论显然成立。时，结论显然成立。设当设当|x|=k|x|=k是结论成立，往证当是结论成立，往证当|x|=k+1|x|=k+1时结论成时结论成立。立。不妨设不妨设x=yax=ya，其中，其中|y|=k |y|=k 462. 正则语言的封闭性正则语言的封闭性 (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) 472. 正则语言的封闭性正则语言