《正则语言的性质》PPT课件

《《正则语言的性质》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、记构成的非空子串可以重复任意多次。q1qkqj4泵引理5泵引理M=(Q,∑,δ,q0,F)

3、Q

4、=Nz=a1a2…am,m≥Nδ(q0,a1a2…ah)=qh状态序列q0,q1,…,qN中，至少有两个状态是相同：qk=qjδ(q0,a1a2…ak)=qkδ(qk,ak+1…aj)=qj=qkδ(qj,aj+1…am)=qm因此，可设z=uvw，其中u=a1a2…ak，v=ak+1…aj，w=aj+1…am6泵引理对于任意的整数i≥0δ(qk,(ak+1…aj)i)=δ(qk,(ak+1…aj)i-1)…=δ(qk,ak+1…aj

5、)=qk故δ(q0,a1a2…ak(ak+1…aj)iaj+1…am)=qm也就是说，a1a2…ak(ak+1…aj)iaj+1…am∈L(M)即uviw∈L。7泵引理(pumpinglemma)设L为一个正则语言，则存在仅依赖于L的正整数N，对于z∈L，如果

6、z

7、≥N，则存在u,v,w，满足(1)z=uvw；(2)

8、uv

9、≤N；(3)

10、v

11、≥1；(4)对于任意的整数i≥0，uviw∈L；(5)N不大于接受L的最小DFAM的状态数。我们总能够在离z的开始处不太远的地方找到一个非空的串v，然后可以把它看作一个“泵”，重复v任意多

12、次，或者去掉它，而所得到的结果串仍然属于L。8例5-1证明{0n1n

13、n≥1}不是RL。证明：假设L={0n1n

14、n≥1}是RL。不妨设N是泵引理所指的仅依赖于L的正整数，取z=0N1N，则z∈L。按照泵引理所述，存在u,v,w，使得z=uvw。由于

15、uv

16、≤N，

17、v

18、≥1，所以v只能由0组成，可设v=0k，k≥1此时有，u=0N-k-j,w=0j1N从而有，uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N当i=2时，有：uv2w=0N+(2-1)k1N=0N+k1N注意到k≥1，所以，N+k>N。这就是说，0N

19、+k1NL。这与泵引理矛盾。所以，L不是RL。9例5-2证明{0n

20、n为素数}不是RL。证明：假设L={0n

21、n为素数}是RL。取z=0N+p∈L，N+p是素数。不妨设v=0k，k≥1从而有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)注意到k≥1，所以N+p+(N+p+1-1)k=(N+p)(1+k)不是素数。故当i=N+p+1时，uvN+p+1w=0(N+p)(1+k)L这与泵引理矛盾。所以

22、，L不是RL。10例5-3证明{0n1m2n+m

23、m,n≥1}不是RL。证明：假设L={0n1m2n+m

24、m,n≥1}是RL。取z=0N1N22N设v=0kk≥1从而有uviw=0N-k-j(0k)i0j1N22N=0N+(i-1)k1N22Nuv0w=0N+(0-1)k1N22N=0N-k1N22N注意到k≥1，N-k+N=2N-k<2N0N-k1N22NL这个结论与泵引理矛盾。所以，L不是RL。11泵引理的说明用来证明一个语言不是RL不能用泵引理去证明一个语言是RL。(1)由于泵引理给出的是RL的必要条件，所以，在用它证明

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

26、z

27、≥N，一定会存在u,v,w，使uviw∈L对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。12泵引理的说明(4)当一个特意被选来用作“发现矛盾”的z确定以后，就必须依

28、照

29、uv

30、≤N和

31、v

32、≥1的要求，说明v不存在(对“存在u,v,w”的否定)。(5)与选z时类似，在寻找i时，我们也仅需要找到一个表明矛盾的“具体”值就可以了(对“所有i”的否定)。(6)一般地，在证明一个语言不是RL的时候，我们并不使用泵引理的第(5)条。(7