陈文宇有限自动机作业参考答案发布

仅限2016年春季周益民B418授课100人班使用2016年3月9日课程名称有限自动机理论授课专计算机科学与技术信息安全班级2015级课程编号0600340修课人数100课程类型必修公共基础课()；学位课(√)；专业核心课()选修专业选修()；任选课（）；公选课()；理论课(√)；实践课()授课方式课堂讲授为主（√）；实验为主（）；自学为主（）；专题讨论为主（）；其他：是否采用多媒体授课是考核方式及成绩构成考试(√)考查(√)考试成绩构成及比例：作业20%+期末80%考查成绩构成及比例：作业100%是否采用双语教学否学时分配讲授40学时；教材名称作者出版社及出版时间有限自动机理论2版陈文宇、田玲、程伟、刘贵松电子工业出版社，2013参考书目形式语言与自动机理论(第2版)形式语言与自动机IntroductiontoAutomataTheory,LanguagesandComputation.Introductiontothetheoryofcomputation.蒋宗礼,姜守旭.陈有祺.JohnEHopcroft,jeffreyDUllman.MichaelSipser清华大学出版社,2007南开大学出版社,2003Addison-Wesleg,1979NewYork:Thomson,1996授课时间第1周——第10周20161第1章基础知识第一章基础知识1.4设∑0,1，请给出下列语言的形式表示。(1)所有以0开头的串形成的语言。 00,1∗ 001∗(2)所有以0开头、以1结尾的串形成的语言。 00,1∗1 0011(3)所有以11开头、以11结尾的串形成的语言。 110,1∗11∪11,111 111111101∗11(4)所有最多有一对连续的0的语言。 01,1∗ε,00∗10,1∗ 011∗00∗10,1∗ (5)所有长度为偶数的串形成的语言。 00,01,10,11∗ 00011011∗(6)所有长度为奇数的串形成的语言。 0,100,01,10,11∗ 0100011011∗(7)所有包含子串01011的串形成的语言。 0,1∗010110,1∗(8)所有包含3个连续0的串形成的语言。 0,1∗0000,1∗(9)所有正数第10个字符是0的串形成的语言。 0,100,1∗ 01001∗(10)所有倒数第6个字符是0的串形成的语言。 0,1∗00,1 01∗001 1.5设和是集合a,b,c,d,e上的二元关系：,,,,,,,,,,,,,,,,,,求○，○，，，∗，∗。○,,,,,,,○a,b,b,d,d,d,e,e,c,b,,,,,,,,,,,,,,,,,∗,,,,,,,,,,,,,,,,,,,,,,,,,20162第2章形式语言第二章形式语言2.1设|,，试构造满足要求的文法G.(1)G是RG。右线性文法：S→OS|OAA→1A|1(2)G是CFG，但不是RG。上下文无关文法：S→ABS→OA|0B→1B|1(3)G是CSG，但不是CFG。左串右串S→AB AB→AAB|ABBA→0B→0(4)G是短语结构文法，但是不是CSG。串可以推短允许出现空串S→0AB1|01S→0A0A→00A|0 A→0A|εB1→B11|1A→0A|ε2.2设 ∑0,1，请给出∑上的下列语言的文法(1)所有以0开头的串。(2)所有以0开头、以1结尾的串。 S→0AS→0A A→0A|1A|0|1 A→1|0A|1A(3)所有以11开头、以11结尾的串。(6)所有长度为偶数的串。S→11A|11|111S→00S|01S|10S|11S|00|01|10|11 A→AA|0A|1A(7)所有包含子串01011的串。(8)所有包含3个连续0的串。S→A0|011A|01011S→A000A|00020163第2章形式语言A→0A|1A|0|1A→0A|1A|0|12.3设 ∑,,，构造下列语言的文法。(1)| 0S→aSb|ε(2)|,1S→ABA→aA|aB→bB|b(3) | ,1S→aAB AB→BAaB→abbB→bbbA→baaA→aa(4)|,,1S→ABAA→aA|aB→bB|b(5) | ∈∑，∈∑S→aAa A→aA|bA|a|b|c(6)|,∈u‘9∑S→aSa|bSb|cSc|WW→aW|bW|cW|a|b|c(7) |,∈∑S→aSa|bSb|cSc|aa|bb|cc|a|b|c(8)|,∈∑S→XWX→aXa|bXb|cXc|aa|bb|ccWaW|bW|cW|a|b|c2.4消除下列文法中的左递归(I)→|||a|b|cA→aA|aB|bB|cBB→bB|cB|ε(II) →||→| →| 20164第3章有限状态自动机第三章3.1构造接收下列语言的DFA。(1)0,1∗(2)0,1(3)|∈0,1且中不含形如00的子串(4)|∈0,1∗且中不含形如00的子串(5) |∈0,1且中含形如10110的子串(6) |∈0,1且中不含形如10110的子串(7) |∈0,1且当把视为二进制数时，模5与3同余，要求为0时，||1,且x0时，的首字符为120165第3章有限状态自动机(8)|∈0,1且的第10个字符是1(9)|∈0,1且以0开头，以1结尾(10)|∈0,1且至少含有两个1(11)|∈0,1且如果以1结尾，则长度为偶数；如果以0结尾，则长度为奇数20166第3章有限状态自动机(12)|是十进制非负实数(13) ∅ (14)ε3.2构造接收下列语言的NFA。(1)|∈0,1且中不含形如00的子串(2) |∈0,1且中含形如10110的子串20167第3章有限状态自动机(3) |∈0,1且中不含形如10110的子串(4) |∈0,1且的倒数第10个字符是1，且以01结尾(5) |∈0,1且以0开头，以1结尾(6) |∈0,1且至少含有两个120168第3章有限状态自动机(7)|∈0,1∗且如果以1结尾，则长度为偶数；如果以0结尾，则长度为奇数(8)|∈0,1∗且的首字符与尾字符相等(9)| ,∈0,13.3根据文法，构造相应的NFA。→|→|||→|||||20169第5章下推自动机第五章下推自动机5.1构造接收下列语言的PDA。(1)10|1(2)101|,1read,1,Z,read,AZ ,1,,,read,0,A,match,,0,,,read,1,A,read,AA,0,,,match,0,A,match,,1,,,match,,Z,match,,1,,,match,,A,match,(3)1010|,1(4)01|2,1,,,,0,Z,,AAZ,1,,,,1,A,,,0,,,,1,A,,,0,,,,,A,,,1,,,,,,,,0,,,,0,,,,0,,,,1,,,(5)含有相同个数的0和1的所有的0,1串(6)2|∈0,1∗,0,,,,1,,,,0,,,,1,,,,0,,,,1,,,,1,,,,0,,,,0,,,201610第5章下推自动机(7)|∈0,1∗用Z表示栈顶read,A,Z,read,AZread,B,Z,read,BZread,,Z,match,Zmatch,a,A,match,match,b,B,match,match,,,match,5.2构造单态的PDA接收语言|∈,。Z表示A,B,为顶的栈read,a,A,match,AZread,b,B,match,BZread,C,A,match,Aread,C,B,match,Bread,a,A,match,read,b,B,match,read,,,match,201611第6章图灵机第六章图灵机I.构造单道图灵机识别语言L10|1①1+0+格式合法性检查start,1,sea_1,1,Rsea_1,1,sea_1,1,Rsea_1,0,sea_0,0,Rsea_0,0,sea_0,0,Rsea_0,0,first,0,L②移动至纸带开始处first,0,first,0,Lfirst,1,first,1,Lfirst,├,newst,├,R③检查1和0的个数是否相等newst,1,del_0,#,Rdel_0,1,del_0,1,Rdel_0,#,del_0,#,Rdel_0,0,sek_1,#,Lsek_1,#,sek_1,#,Lsek_1,1,del_0,#,Rsek_1,├,check,├,R④nm时寻0到达Bdel_0,B,accept,B,N⑤ 检查n=m时是否合法check,#,check,#,Rcheck,0,accept,0,N201612第6章图灵机II.构造单道图灵机接收语言Labc|,0①a+b+c+格式合法性检查，读写头抵达串末尾start,a,sta_b,a,Rsta_b,a,sta_b,a,Rsta_b,b,sta_c,b,Rsta_c,b,sta_c,b,Rsta_c,c,sta_c,c,Rsta_c,B,begin,B,L②删除第一个c，左巡删除最近b或abegin,c,l_del,!,Ll_del,!,l_del,!,Ll_del,$,l_del,$,Ll_del,#,l_del,#,Ll_del,b,r_del,$,Rl_del,a,r_del,#,R③右巡删除c，删除一个就近b或ar_del,#,r_del,#,Rr_del,$,r_del,$,Rr_del,!,r_del,!,Rr_del,c,l_del,!,L④边界情况，右巡到达边界B，左巡检查b和a是否用完r_del,B,check,B,Lcheck,!,check,c,Lcheck,$,check,$,Lcheck,#,check,#,Lcheck,├,accept,├,R201613第6章图灵机III.构造单道图灵机接收语言Labc|,0①a+b+c+格式合法性检查，读写头置于a串的末尾处start,a,sta_b,a,Rsta_b,a,sta_b,a,Rsta_b,b,sta_c,b,Rsta_c,b,sta_c,b,Rsta_c,c,sta_c,c,Rsta_c,B,begin,B,Lbegin,c,begin,c,Lbegin,b,begin,b,Lbegin,a,q0,a,N②删除一个a，将b与c串做一次匹配q0,a,q1,#,R//q0转q1时，位置到达a串的最右a状态q1,#,q1,#,Rq1,$,q1,$,Rq1,b,q2,$,R//q1转q2时，位置到达b串的最左b状态q2,b,q2,b,Rq2,$,q2,$,Rq2,!,q2,!,Rq2,c,q3,!,Lq3,!,q3,!,Lq3,$,q3,$,Lq3,b,q2,$,R//q3转q2时，位置到达b串的最右b状态q3,#,q4,#,R//q3转q4时，b串已经用完q4,$,q4,b,Rq4,!,q5,!,L//恢复b串全文q5,b,q5,b,Lq5,#,q5,#,Lq5,a,q0,a,N//q5转q0时，位置到达a串的最右a状态③边界情况，a串用完为空，左巡到达边界├，检查串合法q5,├,check,├,Rcheck,#,check,a,Rcheck,b,check,b,Rcheck,!,check,c,Rcheck,B,accept,B,N201614第6章图灵机IV.构造单道图灵机接收语言La|2,0①将第一个a改作#，读写头置于#串的最左端start,a,q0,#,N②将#串与右方a串做等长匹配检查q0,#,q1,$,Rq1,#