计算机科学与技术学科前沿丛书 形式语言与自动机PDF电子书下载
- 电子书积分:9 积分如何计算积分?
- 作 者:朱保平,李千目编著
- 出 版 社:北京:清华大学出版社
- 出版年份:2015
- ISBN:9787302399759
- 页数:152 页
第1章 计算理论基础 1
1.1 集合的基本概念 1
1.1.1 集合的定义 1
1.1.2 集合的表示 1
1.1.3 集合间的关系 1
1.1.4 集合的运算 2
1.2 关系 3
1.2.1 二元关系 3
1.2.2 二元关系的性质 3
1.2.3 等价关系 3
1.2.4 递归定义与归纳证明 4
1.3 图与树 6
1.3.1 无向图 7
1.3.2 有向图 7
1.3.3 树 8
1.3.4 二叉树 8
1.4 三个重要概念 9
习题 10
第2章 文法与语言 13
2.1 启示 13
2.2 文法的形式定义 14
2.3 文法的构造 15
2.4 文法的Chomsky体系 16
习题 18
第3章 上下文无关文法及其语言 20
3.1 上下文无关文法 20
3.1.1 派生与派生树 20
3.1.2 文法的二义性 23
3.2 文法和语言的讨论 24
3.3 句法分析 27
3.3.1 最左派生和不确定性 27
3.3.2 文法图 28
3.3.3 广度优先自顶向下句法分析 29
3.3.4 深度优先自顶向下分析 30
3.3.5 自底向上分析 32
3.4 上下文无关文法的化简 38
3.4.1 无用符号 38
3.4.2 消除ε产生式 38
3.4.3 消除单一产生式 39
3.4.4 消除左递归 40
3.5 Chomsky范式 44
3.6 Greibach范式 46
习题 48
第4章 有穷状态自动机 54
4.1 语言的识别 54
4.2 有穷状态自动机的形式定义 55
4.3 确定的有穷自动机 55
4.4 状态转换图 57
4.5 不确定的有穷自动机 58
4.6 NFA与DFA的等价 60
4.7 带空转移的NFA 63
4.8 ε-NFA的确定化 65
4.9 DFA最小化 66
习题 70
第5章 正则语言和正则文法 73
5.1 正则表达式 73
5.1.1 正则表达式的定义 73
5.1.2 正则语言 73
5.2 有穷自动机和正则语言 74
5.2.1 正则表达式到有穷自动机 74
5.2.2 有穷自动机到正则表达式 76
5.3 正则文法和有穷自动机 78
5.3.1 正则文法 78
5.3.2 正则文法与NFA 81
习题 85
第6章 正则语言的性质 87
6.1 正则语言的封闭性 87
6.1.1 简单运算的封闭性 87
6.1.2 其他运算的封闭性 88
6.2 非正则语言的识别 91
6.2.1 鸽巢原理 92
6.2.2 泵引理 92
6.3 Myhill Nerode定理 94
6.4 正则语言的判定算法 99
习题 100
第7章 下推自动机与上下文无关文法 101
7.1 非确定型下推自动机 101
7.1.1 下推自动机的定义 101
7.1.2 下推自动机接受的语言 102
7.2 下推自动机与上下文无关文法 104
7.2.1 上下文无关语言相应的下推自动机 104
7.2.2 下推自动机与相应的上下文无关文法 106
7.3 确定型下推自动机 109
7.4 双栈自动机 110
习题 111
第8章 上下文无关语言的性质 114
8.1 上下文无关文法的泵引理 114
8.2 上下文无关语言的封闭性 116
8.3 上下文无关语言的可判定性 118
习题 118
第9章 图灵机 120
9.1 标准图灵机 120
9.1.1 图灵机的形式定义 120
9.1.2 图灵机识别器 122
9.1.3 图灵机转换器 124
9.2 完成复杂任务的图灵机 126
习题 128
第10章 图灵机的其他模型 130
10.1 带不动选择图灵机 130
10.2 多道图灵机 131
10.3 单向无穷带图灵机 132
10.4 离线图灵机 133
10.5 多带图灵机 134
10.6 多头图灵机 137
10.7 非确定型图灵机 138
10.8 线性界限自动机 140
习题 141
第11章 其他计算模型 143
11.1 递归函数 143
11.1.1 递归函数 143
11.1.2 递归函数的扩展理解 146
11.2 波斯特系统 148
11.3 重写系统 149
11.3.1 矩阵文法 149
11.3.2 马尔可夫算法 150
习题 151
参考文献 152
- 《《走近科学》精选丛书 中国UFO悬案调查》郭之文 2019
- 《新编历史小丛书 祖逖北伐》何兹全著 2019
- 《国际经典影像诊断学丛书 消化影像诊断学 原著第3版》王振常,蒋涛,李宏军,杨正汉译;(美)迈克尔·P.费德勒 2019
- 《本草古籍辑注丛书 第1辑 《食疗本草》辑校》(唐)孟诜撰;(唐)张鼎增补;尚志钧辑校 2019
- 《复旦大学新闻学院教授学术丛书 新闻实务随想录》刘海贵 2019
- 《中国朝鲜族民间故事丛书 阿里郎 朝》李龙得 2019
- 《雨花台烈士传丛书·孙津川传》肖振才著 2018
- 《幼儿园课程资源丛书 幼儿园语言教育资源》周兢编 2015
- 《中国经典文化走向世界丛书 学术卷 2》龚海燕译 2019
- 《学校课程发展丛书 品牌培育与学校课程》林青荻,刘佳责任编辑;(中国)段立群 2019
- 《市政工程基础》杨岚编著 2009
- 《家畜百宝 猪、牛、羊、鸡的综合利用》山西省商业厅组织技术处编著 1959
- 《《道德经》200句》崇贤书院编著 2018
- 《高级英语阅读与听说教程》刘秀梅编著 2019
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《看图自学吉他弹唱教程》陈飞编著 2019
- 《法语词汇认知联想记忆法》刘莲编著 2020
- 《培智学校义务教育实验教科书教师教学用书 生活适应 二年级 上》人民教育出版社,课程教材研究所,特殊教育课程教材研究中心编著 2019
- 《国家社科基金项目申报规范 技巧与案例 第3版 2020》文传浩,夏宇编著 2019
- 《流体力学》张扬军,彭杰,诸葛伟林编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《大学生心理健康与人生发展》王琳责任编辑;(中国)肖宇 2019
- 《大学英语四级考试全真试题 标准模拟 四级》汪开虎主编 2012
- 《大学英语教学的跨文化交际视角研究与创新发展》许丽云,刘枫,尚利明著 2020
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《复旦大学新闻学院教授学术丛书 新闻实务随想录》刘海贵 2019
- 《大学英语综合教程 1》王佃春,骆敏主编 2015
- 《大学物理简明教程 下 第2版》施卫主编 2020
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019