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

有限自动机理论 习 题 册 仅限 2016 年春季周益民 B418 授课 100 人班使用 2016 年 3 月 9 日 课程名称 有限自动机理论 授 课 专 计算机科学与技术 信息安全 班级 2015 级 课程编号 0600340 修课人数 100 课程类型 必修 公共基础课( )；学位课 ( )；专业核心课( ) 选修 专业选修( )；任选课（ ） ；公选课( )； 理论课( )；实践课( ) 授课方式 课堂讲授为主（ ） ；实验为主（ ） ； 自学为主（ ） ；专题讨论为主（ ） ； 其他： 是否采用 多媒体授课 是 考核方式及 成绩构成 考 试( )考 查( ) 考试成绩构成及比例：作业 20%+期末 80% 考查成绩构成及比例：作业 100% 是否采用 双语教学 否 学时分配 讲授 40 学时； 教材 名称 作者 出版社及出版时间 有限自动机理论 2 版 陈文宇、 田玲、 程伟、 刘贵松 电子工业出版社，2013 参考书目 形式语言与自动机理论 (第 2 版) 形式语言与自动机 Introduction to Automata Theory, Languages and Computation. Introduction to the theory of computation. 蒋宗礼,姜守旭. 陈有祺. John E Hopcroft ,jeffrey D Ullman . Michael Sipser 清华大学出版社, 2007 南开大学出版社, 2003 Addison-Wesleg, 1979 New York: Thomson, 1996 授课时间 第 1 周第 10 周 有限自动机理论习题参考答案 2016 1 第 1 章 基础知识 第一章第一章 基础知识基础知识 1.4 设 ? ?0,1?，请给出下列语言的形式表示。 (1) 所有以 0 开头的串形成的语言。 ?0?0,1? 0?0 ? 1? (2) 所有以 0 开头、以 1 结尾的串形成的语言。 ?0?0,1?1 0?0 ? 1?1 (3) 所有以 11 开头、以 11 结尾的串形成的语言。 ?11?0,1?11? ?11,111? ?11 ? 111 ? ?11?0 ? 1?11? (4) 所有最多有一对连续的 0 的语言。 ?01,1?,00?10,1? ?01 ? 1?00?10,1? (5) 所有长度为偶数的串形成的语言。 ?00,01,10,11? ?00 ? 01 ? 10 ? 11? (6) 所有长度为奇数的串形成的语言。 ?0,1?00,01,10,11? ?0 ? 1?00 ? 01 ? 10 ? 11? (7) 所有包含子串 01011 的串形成的语言。 ?0,1?01011?0,1? (8) 所有包含 3 个连续 0 的串形成的语言。 ?0,1?000?0,1? (9) 所有正数第 10 个字符是 0 的串形成的语言。 ?0,1?0?0,1? ?0 ? 1?0?0 ? 1? (10) 所有倒数第 6 个字符是 0 的串形成的语言。 ?0,1?0?0,1? ?0 ? 1?0?0 ? 1? 1.5 设 ? 和 ? 是集合 ? ? ?a,b,c,d,e? 上的二元关系： ? ?,?,?,?,?,?,?,?,?,? ? ?,?,?,?,?,?,?,?,?,? 求? ?，? ?，? ?，?，?，?。 ? ? ?,?,?,?,?,?,?,? ? ? ?a,b?,?b,d?,?d,d?,?e,e?,?c,b? ? ? ? ?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,? ? ? ?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,? 有限自动机理论习题参考答案 2016 2 第 2 章 形式语言 第二章第二章 形式语言形式语言 2.1 设? ? ?|?,? ? ?，试构造满足要求的文法 G. (1) G 是 RG。 右线性文法： S OS|OA A 1A|1 (2) G 是 CFG，但不是 RG。 上下文无关文法： S AB S OA|0 B 1B|1 (3) G 是 CSG，但不是 CFG。 左串m 时寻 0 到达 B 检查 n=m 时是否合法 有限自动机理论习题参考答案 2016 12 第 6 章 图灵机 II. 构造单道图灵机接收语言L ? ?a?b?c?|?,? ? 0? a+b+c+格式合法性检查，读写头抵达串末尾 删除第一个 c，左巡删除最近 b 或 a 右巡删除 c，删除一个就近 b 或 a 边界情况，右巡到达边界 B，左巡检查 b 和 a 是否用完 有限自动机理论习题参考答案 2016 13 第 6 章 图灵机 III. 构造单道图灵机接收语言L ? ?a?b?c?|?,? ? 0? a+b+c+格式合法性检查，读写头置于 a 串的末尾处 删除一个 a，将 b 与 c 串做一次匹配 / q0 转 q1 时，位置到达 a 串的最右 a 状态 / q1 转 q2 时，位置到达 b 串的最左 b 状态 / q3 转 q2 时，位置到达 b 串的最右 b 状态 / q3 转 q4 时，b 串已经用完 / 恢复 b 串全文 / q5 转 q0 时，位置到达 a 串的最右 a 状态 边界情况，a 串用完为空，左巡到达边界，检查串合法 有限自动机理论习题参考答案 2016 14 第 6 章 图灵机 IV. 构造单道图灵机接收语言L ? ?a?|? ? 2?,? ? 0? 将第一个 a 改作#，读写头置于#串的最左端 将#串与右方 a 串做等长匹配检查 / 隐含地 q1 若遇到 B 是非法拒绝的 #串用完到达左边界 / 刚好匹配完，接收 / 还有剩余 a，将#串做长 / q0 读写头置于#串的最左端 有限自动机理论习题参考答案 2016 15 第 6 章 图灵机 V 构造三道图灵机实现二进制正整数加法? ? ?。 没有进位 有进位 两位数长度不一致 结束 有限自动机理论习题参考答案 2016 16 第 6 章 图灵机 VI 构造三道图灵机实现二进制正整数减法? ? ?，? ? ?。 没有退位 有退位 两位数长度不一致 结束 编写者的话：此