《0201d31d4regularlanguage100114》由会员分享，可在线阅读，更多相关《0201d31d4regularlanguage100114（55页珍藏版）》请在金锄头文库上搜索。
1、ChjTang CS_Dept.Sichuan Univ.可计算理论Book :计算理论导引 Introduction to the Theory of Computation Chapter 1&2 RL, pumping lemma .CFL Professor. : 唐常杰TangC Http:/ : Phd ，MS in CS . 2000-2009, SCUStyle : Lecture / Seminar 2024/9/151ChjTang CS_Dept.Sichuan Univ.可计算理论 2024/9/152ChjTang CS_Dept.Sichuan Univ.可计算理论
2、2024/9/153ChjTang CS_Dept.Sichuan Univ.可计算理论 今天课程 两个PPT Chapter 1: RE = Regular Languages, non-regular languages RL pumping lemma Chapter 2: Context-Free Languages (CFLs)2024/9/154ChjTang CS_Dept.Sichuan Univ.可计算理论国庆换课程时间n10.8 （星期4） 10.10 星期日 下午2024/9/155ChjTang CS_Dept.Sichuan Univ.可计算理论复习上次复习上次 复习
3、上次复习上次 的要点的要点 自动机的合成自动机的合成 并机识并语，串机并机识并语，串机 识识 连语，连语， 打圈之别星语打圈之别星语 正规语言正规语言 Today Regular ExpressionsRegular Expressions 2024/9/156ChjTang CS_Dept.Sichuan Univ.可计算理论Regular Expressions (Def. 1.26 )(Def. 1.26 ) ep64 cp38ep64 cp38例 数学模型：N! ，denoted as F(N)， is defined as F(0)=1; /递归基础 （程序终止条件）F(N)=NF(
4、N-1) if N = 1 /递归 (减1）结构程序实现：Int Factor(int n) if (n= 1 /递归 (减1）结构程序实现：Int Factor(int n) if (nn时，至少有一个地方在打圈, (发言激动时尤其如此），以后遇此，可笑谈： Pumping Pumping THoeremTHoerem is working is working 正则语言是靠打圈，来描述（有某种规律的）无限集合2024/9/1531ChjTang CS_Dept.Sichuan Univ.可计算理论Repeating DFA Paths ep79 cp48 （思想）q1qkqjConside
5、r an accepting DFA M with size |Q| 机器状态数On a string of length p, p+1 states（识别某词的状态路径长度） get visited For p|Q|, there must be a j such that the computational path looks like: q1,qj,qj,qk第一个打圈的地方前面一段没有重复2024/9/1532ChjTang CS_Dept.Sichuan Univ.可计算理论Repeating DFA Paths ep79 cp47 （思想）q1qkqjThe action of
6、the DFA in qj is always the same.If we repeat (or ignore) the qj,qj part, the newpath will again be an accepting path 不确定自动机，多路并行打圈，语无伦次 即 不确定2024/9/1533ChjTang CS_Dept.Sichuan Univ.可计算理论 定理需要 ”足够长的串“ ，有实例吗？ DNA序列 字母表上 G, C, A ,T 人类最短的18号染色体 C18 in * 长度 |C18| 4.21062024/9/1534ChjTang CS_Dept.Sichuan
7、 Univ.可计算理论Pumping Lemma (Pumping Lemma (ThmThm 1.37) cp47 1.37) cp47 （形式化表述）（形式化表述）For every regular language L, there is a pumping length p, such that for any string sL and |s|p, we can write s=xyz with1) x yi z L for every i0,1,2, 中间罗嗦2) |y| 13) |xy| p 开讲后不久，就打圈Note that 1) implies that xz L（重要）
8、2) says that y cannot be the empty string Condition 3) is not always used 经得起泵测试（容忍罗嗦） 是RL的必要条件（不充分）2024/9/1535ChjTang CS_Dept.Sichuan Univ.可计算理论Pumping Lemma (Thm 1.37) ep78For every regular language L, there is a pumping length p, such that for any string sL and |s|p, we can write s=xyz with1) x y
9、i z L for every i0,1,2, 中间罗嗦2) |y| 03) |xy| p 开讲后不久，就打圈Note that 1) implies that xz L（重要） 2) says that y cannot be the empty string Condition 3) is not always used 经得起泵测试（容忍罗嗦） 是RL的必要条件（不充分）长度超过自动机状态数的单词必有一处y 打圈（真圈）2024/9/1536ChjTang CS_Dept.Sichuan Univ.可计算理论Pumping Lemma (Thm 1.37) ep78For every r
10、egular language L, there is a pumping length p, such that for any string sL and |s|p, we can write s=xyz with1) x yi z L for every i0,1,2, 中间罗嗦2) |y| 03) |xy| p 开讲后不久，就打圈Note that 1) implies that xz L（重要） 2) says that y cannot be the empty string Condition 3) is not always used 长度超过自动机状态数的单词必有一处y 打圈
11、（真圈）经得起泵测试（容忍罗嗦，有容乃正） 是RL的必要条件（但不是充分条件）2024/9/1537ChjTang CS_Dept.Sichuan Univ.可计算理论Formal Proof of Pumping LemmaFormal Proof of Pumping Lemma ep78 ep78 证明细节，自学证明细节，自学Let M = (Q,q1,F) with Q = q1,qpLet s = s1snL(M) with |s| = n p 泵长为状态数 Computational path of M on s is thesequence r1,rn+1 Qn+1 withr1
12、 = q1, rn+1F and rt+1= (rt,st) for 1tnBecause n+1 p+1, there are two statessuch that rj = rk (with jk and k p+1)Let x = s1sj1, y = sjsk1, and z = sksn+1x takes M from q1=r1 to rj, y takes M from rj to rj, and z takes M from rj to rn+1FAs a result: xyiz takes M from q1 to rn+1F (i 0)鸽巢原理至少一处打圈2024/9/
13、1538ChjTang CS_Dept.Sichuan Univ.可计算理论Formal Proof of Pumping LemmaFormal Proof of Pumping Lemma ep78 ep78 证明细节，自学证明细节，自学Let M = (Q,q1,F) with Q = q1,qpLet s = s1snL(M) with |s| = n p 泵长为状态数 Computational path of M on s is thesequence r1,rn+1 Qn+1 withr1 = q1, rn+1F and rt+1= (rt,st) for 1tnBecause
14、n+1 p+1, there are two statessuch that rj = rk (with jk and k p+1)Let x = s1sj1, y = sjsk1, and z = sksn+1x takes M from q1=r1 to rj, y takes M from rj to rj, and z takes M from rj to rn+1FAs a result: xyiz takes M from q1 to rn+1F (i 0)鸽巢原理至少一处打圈2024/9/1539ChjTang CS_Dept.Sichuan Univ.可计算理论Formal P
15、roof of Pumping Lemma ep78Formal Proof of Pumping Lemma ep78证明细节，自学证明细节，自学Let M = (Q,q1,F) with Q = q1,qpLet s = s1snL(M) with |s| = n pComputational path of M on s is thesequence r1,rn+1 Qn+1 withr1 = q1, rn+1F and rt+1= (rt,st) for 1tnBecause n+1 p+1, there are two terms such that rj = rk (with jj
16、 | ij 非正则非正则ExcExc 1.42 1.42 ep81, cp50ep81, cp501.失败的试探 : pumping up 试用 s=0p11p,S=xyz, with y=0k gives,xyyz = 0p+k1p, xy3z = 0p+2k1p, which are all in E 无矛盾，要另辟蹊径2.再探索 i=0: pump down to xz = 0pk1p. Overall for s = xyz = 0p1p (with |xy|p): y=0k, hence xz = 0pk1p EE 经不起泵的测试，Contradiction: E is not re
17、gular2024/9/1551ChjTang CS_Dept.Sichuan Univ.可计算理论Pumping Down Pumping Down 求证求证 E = 0E = 0i i1 1j j | ij | ij 非正则非正则ExcExc 2.42 2.42 ep81, cp51ep81, cp511.失败的试探 : pumping up 试用 s=0p11p,S=xyz, with y=0k gives,xyyz = 0p+k1p, xy3z = 0p+2k1p, which are all in E 无矛盾，要另辟蹊径2.再探索 i=0: pump down to xz = 0pk
18、1p. Overall for s = xyz = 0p1p (with |xy|p): y=0k, hence xz = 0pk1p EE 经不起泵的测试，Contradiction: E is not regular2024/9/1552ChjTang CS_Dept.Sichuan Univ.可计算理论小结nChapter 1: H RE = Regular Languages, H nonregular languagesH RL pumping lemma n Chapter 2:H Context-Free Languages (CFLs)H下面接着讲下面接着讲 02_02d1_CFL_070227.ppt2024/9/1553ChjTang CS_Dept.Sichuan Univ.可计算理论 下面接着讲下面接着讲 02_02d1_CFL_070227.ppt2024/9/1554ChjTang CS_Dept.Sichuan Univ.可计算理论End of Chapter 1 . Any Question ?End of Chapter 1 . Any Question ?Thank you !2024/9/1555
