第五章 正则语言的性质

《第五章 正则语言的性质》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第五章正则语言的性质习题：题2、题6、题11；题12中任选一小题第五章正则语言的性质正则语言的泵引理正则语言运算的封闭性自动机的极小化正则语言的判定算法*正则语言的泵引理分析：1、识别RL句子的DFA仅有有限个状态。2、用DFAM接受无穷语言L，L中一定存在一个足够长的句子，使得DFA在识别该句子时，需要重复地经过某些状态。DFA处理句子经历的状态序列DFA处理句子经历的重复状态序列正则语言的泵引理RL特征的形式化描述：1、假设L是RL，DFAM=，满足L(M)=L，M具有有限个状态，即，

2、Q

3、=N，且Q中状态

4、均为可达状态。2、取L中任意句子z=a1a2…am(m≥N)，并有qm∈F。3、由于m≥N，读字符的状态序列q0,q1,…,qN中至少有两个状态相同。假设状态qk=qj,对于k

5、0,δ(q,aa…a(aa…a)iaa…a)=q∈F012kk+1k+2jj+1j+2mm亦有：aa…a(aa…a)iaa…a∈L（M）12kk+1k+2jj+1j+2m设u=aa…a,v=aa…a,w=aa…a;12kk+1k+2jj+1j+2m对于任意整数i≥0，有：z=uviw∈L;由于k

6、uv

7、≤N,

8、v

9、≥1；z仍然是正则语言RL的句子。正则语言的泵引理定义5-1：泵引理设L为RL，存在仅依赖于语言L的某个正整数N，对于∀z∈L，如果

10、z

11、≥N，则存在u,v,w，满足以下条件：1、z=uvw;2、

12、

13、uv

14、≤N;3、

15、v

16、≥1;4、对于任意整数i≥0，uviw∈L。正则语言的泵引理泵引理应用：用反证法证明给定语言L不是RL。假设L是RL，L应满足泵引理。构造某句子z=uvw∈L，在给定正整数N和某个i的条件下，可证得句子z=uviw不符合语言L中句子的结构特征，即有句子z=uviw不属于RLL。由于L中存在句子z的结构不满足泵引理RL关于“对于任意整数i≥0，uviw∈RLL”的描述条件，与假设矛盾，故证得L不是RL。正则语言的泵引理–应用实例例1：证明语言L={0n

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

18、n为素数}是RL，

19、其满足泵引理。设依赖于L（M）的正整数为N，L中字符串z=0N+p，其中，N+p是素数。根据泵引理，必存在u,v,w,使得z=uvw且

20、v

21、≥1；这里，v是0组成的非空串，不妨设v=0k,（k≥1），w=0j，u=0N+p–k–j，从而有，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)(1+k)不总是素数。所以，当i=N+p+1时，有字符串z=uvN+p+1w=0(N+

22、p)(1+k)∈L，其与泵引理第四条矛盾，所以，L不是RL。正则语言的泵引理–应用实例例2：证明语言L={0n1n

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

24、n≥1}是RL，其应满足泵引理。设依赖于L(M)的正整数为N，L中有字符串为z=0N1N。根据泵引理，必存在u,v,w,构成句子z=uvw，其中

25、uv

26、≤N，

27、v

28、≥1；这里，v只能是由0组成的非空串。不失一般性地可设，v=0k，（k≥1），w=0j1N，u=0N–k-j，从而有，uviw=0N–k-j(0k)i0j1N，取i=2时，有uv2w=0N–k-j(0k)20j1N=

29、0N+k1N由于已知k≥1，有N＜N+k,于是有：字符串z=0N+k1N∈L，与泵引理第四条矛盾，故L不是RL正则语言的泵引理说明：1、泵引理给出关于RL性质的条件是必要条件：若L是RL，其一定满足泵引理给出的4个条件。因此，应用泵引理证明一个语言不是RL时，常用“反证法”。2、泵引理给出的RL性质的条件不是充分条件；满足泵引理所给4个条件的语言不一定就是RL。因此，泵引理只能用于证明给定语言不是RL；而不能证明给定语言是RL。第五章正则语言的性质正则语言的泵引理正则语言运算的封闭性自动机的极小化正则语言运算的封闭性定义5-2：如果对

30、某类语言进行某种运算后，所得的结果仍为该类语言的句子，则称该类语言对此运算是封闭的，或称该类语言对运算具有封闭性。正则语言运算的封闭性定义5-3：称某语言类对某运算满足有效封闭性，是指给定该类语言中任意两个语言L、L的形