1
, ,
, ,
, ,
,
, ,
, ,
, , , , , , , , ,
∗
,
,
第 1 章 基础知识
有限自动机理论习题参考答案
2016
第二章 形式语言
2.1 设
(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。 左串<右串 S → AB AB → AAB|ABB A→0 B→0 (4) G 是短语结构文法，但是不是 CSG。 串可以推短 S → 0AB1|01 0A → 00A|0 B1 → B11|1 允许出现空串 S → 0A A → 0A|ε A → 0A|ε
2 第 2 章 形式语言
有限自动机理论习题参考答案
2016
A → 0A|1A|0|1
A → 0A|1A|0|1
2.3 设 ∑
(1) | S → aSb|ε
, ,
0
，构造下列语言的文法。
(2) | S → AB A → aA|a B → bB|b , 1
(3) S → aAB AB → BA aB → ab bB → bb bA → ba aA → aa (5) |
有限自动机理论 习 题 册
仅限 2016 年春季周益民 B418 授课 100 人班使用
2016 年 3 月 9 日
课程名称 课程编号
有限自动机理论 0600340 必修 公共基础课( 专业选修(
授 课 专 计算机科学与技术 信息安全
班级 修课人数 )
2015 级 100
)；学位课 (√ )；专业核心课( )；任选课（ ) ） ； ） ； ） ；公选课( )；
课程类型
选修
理论课(√ )；实践课(
课堂讲授为主（ √ ） ；实验为主（ 授课方式 自学为主（ 其他： 考 试( √ )考 查( √ ) ） ；专题讨论为主（
是否采用 多媒体授课
是
考核方式及 成绩构成 学时分配 教材
考试成绩构成及比例：作业 20%+期末 80% 考查成绩构成及比例：作业 100% 讲授 40 学时； 名称 作者
∗
00
10,1 ∗
(5) 所有长度为偶数的串形成的语言。 00,01,10,11 ∗ 00
∗
(6) 所有长度为奇数的串形成的语言。 0,1 00,01,10,11 ∗ 0 0,1 ∗ 01011 0,1 0,1 ∗ 000 0,1
∗ ∗
(2) 所有以 0 开头、以 1 结尾的串形成的语言。 1 1 111
∗
(3) 所有以 11 开头、以 11 结尾的串形成的语言。 11 ∪ 11,111 11
∗
11 0
1
∗
11
(4) 所有最多有一对连续的 0 的语言。 ε, 00 10,1 ∗ 01 01 10 1 00 1 11
是否采用 双语教学
否
出版社及出版时间
有限自动机理论 2 版
陈文宇、 田玲、 程伟、 刘贵松
电子工业出版社，2013
形式语言与自动机理论 (第 2 版) 形式语言与自动机 参考书目 Introduction to Automata Theory, Languages and Computation. Introduction to the theory of computation. 授课时间
| ,
1
(4) S → ABA
| A → aA|a B → bB|b
,
,
1
∈ ∑，
∈∑
S → aAa A → aA|bA|a|b|c
(6)
|
,
∈ u‘9∑
S → aSa|bSb|cSc|W W → aW|bW|cW|a|b|c (8) | S → XW X → aXa|bXb|cXc|aa|bb|cc W aW|bW|cW|a|b|c , ∈∑
∗ ∗
01
10
11
∗
(7) 所有包含子串 01011 的串形成的语言。 (8) 所有包含 3 个连续 0 的串形成的语言。 (9) 所有正数第 10 个字符是 0 的串形成的语言。 0,1 0 0,1 ∗ 0 0,1 ∗ 0 0,1 0 1 ∗0 0 1 0 0 1 1
| ,
，试构造满足要求的文法 G.
2.2 设 ∑
S → 0A
0,1 ，请给出∑上的下列语言的文法
(2) 所有以 0 开头、以 1 结尾的串。 S → 0A A → 1|0A|1A S → 00S|01S|10S|11S|00|01|10|11 (8) 所有包含 3 个连续 0 的串。 S → A000A|000
2016
第一章 基础知识
1.4 设 ∑ 0,1 ，请给出下列语言的形式表示。
1
∗
(1) 所有以 0 开头的串形成的语言。 0 0,1 ∗ 0 0 0 0,1 ∗ 1 0 0 11 0,1 01,1
(1) 所有以 0 开头的串。 A → 0A|1A|0|1 S → 11A|11|111 A → AA|0A|1A (7) 所有包含子串 01011 的串。 S → A0|011A|01011
(3) 所有以 11 开头、以 11 结尾的串。 (6) 所有长度为偶数的串。
∗
(10) 所有倒数第 6 个字符是 0 的串形成的语言。
1.5 设
和
是集合
, , , ,
∗
a, b, c, d, e 上的二元关系：
, , ，
∗
, , 。
, ,
, ,
, ,ห้องสมุดไป่ตู้
, ,
, ,
求 ○ ○
○
， , , , ,
○ , , , , ,
， , , , ,
， , , , , , ,
， , , ,
a, b , b, d , d, d , e, e , c, b , , , , ,
蒋宗礼,姜守旭. 陈有祺. John E Hopcroft ,jeffrey D Ullman . Michael Sipser
清华大学出版社, 2007 南开大学出版社, 2003 Addison-Wesleg, 1979
New York: Thomson, 1996
第 1 周——第 10 周
有限自动机理论习题参考答案