有限自动机理论习题册有限自动机原理.pdf

有限自动机理论 习 题 册 姓名 学号 考试 考查 仅限 2016 年秋季 B407 选课使用 2016 年 9 月 18 日 课程名称 有限自动机理论 授 课 专 计算机科学与技术 信息安全 班级 2016 级 课程编号 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 周 第 8 周 有限自动机理论 作业 2016 09 1 第 1 章 基础知识 第一章第一章 基础知识基础知识 1 4 设 请给出下列语言的形式表示 1 所有以 0 开头的串形成的语言 2 所有以 0 开头 以 1 结尾的串形成的语言 3 所有以 11 开头 以 11 结尾的串形成的语言 4 所有最多有一对连续的 0 的语言 5 所有长度为偶数的串形成的语言 6 所有长度为奇数的串形成的语言 7 所有包含子串 01011 的串形成的语言 8 所有包含 3 个连续 0 的串形成的语言 9 所有正数第 10 个字符是 0 的串形成的语言 10 所有倒数第 6 个字符是 0 的串形成的语言 1 5 设 和 是集合 Set 上的二元关系 求 有限自动机理论 作业 2016 09 2 第 2 章 形式语言 第二章第二章 形式语言形式语言 2 1 设 试构造满足要求的文法 G 1 G 是 RG 2 G 是 CFG 但不是 RG 3 G 是 CSG 但不是 CFG 4 G 是短语结构文法 但是不是 CSG 2 2 设 请给出 上的下列语言的文法 1 所有以 0 开头的串 2 所有以 0 开头 以 1 结尾的串 3 所有以 11 开头 以 11 结尾的串 6 所有长度为偶数的串 7 所有包含子串 01011 的串 8 所有包含 3 个连续 0 的串 有限自动机理论 作业 2016 09 3 第 2 章 形式语言 2 3 设 构造下列语言的文法 1 0 2 1 3 1 4 1 5 6 u 9 7 8 2 4 消除下列文法中的左递归 I a b c II 有限自动机理论 作业 2016 09 4 第 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 且x 0时 的首字符为 1 有限自动机理论 作业 2016 09 5 第 3 章 有限状态自动机 8 0 1 且 的第 10 个字符是 1 9 0 1 且 以 0 开头 以 1 结尾 10 0 1 且 至少含有两个 1 11 0 1 且如果 以 1 结尾 则长度为偶数 如果 以 0 结尾 则长度 为奇数 有限自动机理论 作业 2016 09 6 第 3 章 有限状态自动机 12 是十进制非负实数 13 14 3 2 构造接收下列语言的 NFA 1 0 1 且 中不含形如 00 的子串 2 0 1 且 中含形如 10110 的子串 有限自动机理论 作业 2016 09 7 第 3 章 有限状态自动机 3 0 1 且 中不含形如 10110 的子串 4 0 1 且 的倒数第 10 个字符是 1 且以 01 结尾 5 0 1 且 以 0 开头 以 1 结尾 6 0 1 且 至少含有两个 1 有限自动机理论 作业 2016 09 8 第 3 章 有限状态自动机 7 0 1 且如果 以 1 结尾 则长度为偶数 如果 以 0 结尾 则长度为 奇数 8 0 1 且 的首字符与尾字符相等 9 0 1 3 3 根据文法 构造相应的 NFA 有限自动机理论 作业 2016 09 9 第 5 章 下推自动机 第五章第五章 下推自动机下推自动机 5 1 构造接收下列语言的 PDA 1 1 0 1 2 1 0 1 1 3 1 0 1 0 1 4 0 1 2 5 含有相同个数的 0 和 1 的所有的 0 1 串 6 2 0 1 有限自动机理论 作业 2016 09 10 第 5 章 下推自动机 7 0 1 用 Z 表示栈顶 5 2 构造单态的 PDA 接收语言 Z 表示 A B 为顶的栈 有限自动机理论 作业 2016 09 11 第 6 章 图灵机 第六章第六章 图灵机图灵机 I 构造单道图灵机识别语言 有限自动机理论 作业 2016 09 12 第 6 章 图灵机 II 构造单道图灵机接收语言 有限自动机理论 作业 2016 09 13 第 6 章 图灵机 III 构造单道图灵机接收语言 有限自动机理论 作业 2016 09 14 第 6 章 图灵机 IV 构造单道图灵机接收语言 有限自动机理论 作业 2016 09 15 第 6 章 图灵机 V 构造三道图灵机实现二进制正整数加法 有限自动机理论 作业 2016 09 16 第 6 章 图灵机 VI 构造三道图灵机实现二进制正整数减法 编写者的话