是
考核方式及 成绩构成 学时分配 教材
考试成绩构成及比例：作业 20%+期末 80% 考查成绩构成及比例：作业 100% 讲授 40 学时； 名称 作者
是否采用 双语教学
否
出版社及出版时间
有限自动机理论 2 版
陈文宇、 田玲、 程伟、 刘贵松
电子工业出版社，2013
形式语言与自动机理论 (第 2 版) 形式语言与自动机 参考书目 Introduction to Automata Theory, Languages and Computation. Introduction to the theory of computation. 授课时间
(12)
| 是十进制非负实数
(13) ∅
(14) ε
3.2 构造接收下列语言的 NFA。
(1) | ∈ 0,1 且 中不含形如 00 的子串
(2)
| ∈ 0,1 且 中含形如 10110 的子串
6 第 3 章 有限状态自动机
有限自动机理论
作业
2016.09
(3)
| ∈ 0,1 且 中不含形如 10110 的子串
。
10 第 5 章 下推自动机
有限自动机理论
作业
2016.09
第六章 图灵机
I. 构造单道图灵机识别语言 |
11 第 6 章 图灵机
有限自动机理论
作业
2016.09
II. 构造单道图灵机接收语言
|,
12 第 6 章 图灵机
有限自动机理论
作业
2016.09
III. 构造单道图灵机接收语言
|,
13 第 6 章 图灵机
作业
2016.09
第一章 基础知识
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 的串形成的语言。
(3) 1 0 1 0 | ,
1
(4) 0 1 |
2
(5) 含有相同个数的 0 和 1 的所有的 0,1 串
(6)
2
|
∈ 0,1
∗
9 第 5 章 下推自动机
有限自动机理论
作业
∗
2016.09
(7)
|
∈ 0,1
用 Z 表示栈顶
5.2 构造单态的 PDA 接收语言 Z 表示 A, B, 为顶的栈
|
∈
,
有限自动机理论 习 题 册
姓名：__________________ 学号：__________________ 考试□ 考查□
仅限 2016 年秋季 B407 选课使用
2016 年 9 月 18 日
课程名称 课程编号
有限自动机理论 0600340 必修 公共基础课( 专业选修(
授 课 专 计算机科学与技术 信息安全
(8)
| ∈ 0,1 且 的第 10 个字符是 1
(9)
| ∈ 0,1 且 以 0 开头，以 1 结尾
(10)
| ∈ 0,1 且 至少含有两个 1
(11) 为奇数
| ∈ 0,1 且如果 以 1 结尾，则长度为偶数；如果 以 0 结尾，则长度
5 第 3 章 有限状态自动机
有限自动机理论
作业
2016.09
1.5 设
和
是集合 Set
, , , ,
∗
, , , ,
, , ，
∗
上的二元关系：
, , , , ,
, , 。
, ,
, ,
,
求
○
，
○
，
，
，
1 第 1 章 基础知识
有限自动机理论
作业
2016.09
第二章 形式语言
2.1 设
(1) G 是 RG。
| ,
，试构造满足要求的文法 G.
(2) G 是 CFG，但不是 RG。
(4)
| ∈ 0,1 且 的倒数第 10 个字符是 1，且以 01 结尾
(5)
| ∈ 0,1 且 以 0 开头，以 1 结尾
(6)
| ∈ 0,1 且 至少含有两个 1
7 第 3 章 有限状态自动机
有限自动机理论
作业
2016.09
(7) 奇数
| ∈ 0,1 ∗ 且如果 以 1 结尾，则长度为偶数；如果 以 0 结尾，则长度为
班级 修课人数 )
2016 级 100
)；学位课 (√ )；专业核心课( )；任选课（ ) ） ； ） ； ） ；公
课堂讲授为主（ √ ） ；实验为主（ 授课方式 自学为主（ 其他： 考 试( √ )考 查( √ ) ） ；专题讨论为主（
是否采用 多媒体授课
(8)
| ∈ 0,1 ∗ 且 的首字符与尾字符相等
(9)
| ,
∈ 0,1
3.3 根据文法，构造相应的 NFA。
→ | → | | | | | → | | |
8 第 3 章 有限状态自动机
有限自动机理论
作业
2016.09
第五章 下推自动机
5.1 构造接收下列语言的 PDA。
(1) 1 0 | 1 (2) 1 0 1 | , 1
蒋宗礼,姜守旭. 陈有祺. John E Hopcroft ,jeffrey D Ullman . Michael Sipser
清华大学出版社, 2007 南开大学出版社, 2003 Addison-Wesleg, 1979
New York: Thomson, 1996
第 1 周——第 8 周
有限自动机理论
(3) G 是 CSG，但不是 CFG。
(4) G 是短语结构文法，但是不是 CSG。
2.2 设 ∑
,
，请给出∑上的下列语言的文法
(2) 所有以 0 开头、以 1 结尾的串。
(1) 所有以 0 开头的串。
(3) 所有以 11 开头、以 11 结尾的串。 (6) 所有长度为偶数的串。
(7) 所有包含子串 01011 的串。
(I) → | | |a|b|c
(II) → → → | | | |
3 第 2 章 形式语言
有限自动机理论
作业
2016.09
第三章 有限状态自动机
3.1 构造接收下列语言的 DFA。
(1) 0,1
∗
(2) 0,1
(3)
| ∈ 0,1 且 中不含形如 00 的子串
(4)
| ∈ 0,1 ∗ 且 中不含形如 00 的子串
(8) 所有包含 3 个连续 0 的串。
2 第 2 章 形式语言
有限自动机理论
作业
2016.09
2.3 设 ∑
(1) |
, ,
0
，构造下列语言的文法。
(2) | , 1
(3)
| ,
1
(4)
|
,
,
1
(5)
|
∈ ∑，
∈∑
(6)
|
,
∈ u‘9∑
(7)
|
,
∈∑
(8)
|
,
∈∑
2.4 消除下列文法中的左递归
(5)
| ∈ 0,1 且 中含形如 10110 的子串
(6)
| ∈ 0,1 且 中不含形如 10110 的子串
(7) | |
| ∈ 0,1 且当把视为二进制数时， 模 5 与 3 同余，要求 为 0 时， 1,且x 0时， 的首字符为 1
4 第 3 章 有限状态自动机
有限自动机理论
作业
2016.09
有限自动机理论
作业
2016.09
IV. 构造单道图灵机接收语言
|
,
14 第 6 章 图灵机
有限自动机理论
作业
2016.09
V 构造三道图灵机实现二进制正整数加法
。
15 第 6 章 图灵机
有限自动机理论
作业
2016.09
VI 构造三道图灵机实现二进制正整数减法
，
。
编写者的话：此有限自动机习题册共计 16 页系周益民选编，旨在普适性地选择 典型的题型例子给予硕士一年级同学用作练习、复习。周益民教学班当使用此习 题册无虞。若发现有字词、语句、公式、数字、参考答案等任何疏漏，及时反馈 给周益民以作修订为要，yiminzhou@ 。非常期待您的宝贵意见！
16 第 6 章 图灵机