-
内容大纲
本书是形式语言、自动机理论和计算复杂性方面的经典之作,是在国际上得到广泛认可的计算机理论和计算机工程专业的教材。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书注重定义、定理的准确性和严格性,注重形式化和严格的数学推理能力的培养,同时在定义和证明中运用直观的方法说明抽象概念,借助许多图表帮助传达思想,并包含大量难度各异的示例和习题,便于学生加深对内容的理解。
本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。 -
作者介绍
-
目录
译者序
前言
第1章 自动机:方法与体验
1.1 为什么研究自动机理论
1.1.1 有穷自动机简介
1.1.2 结构表示法
1.1.3 自动机与复杂性
1.2 形式化证明简介
1.2.1 演绎证明
1.2.2 求助于定义
1.2.3 其他定理形式
1.2.4 表面上不是“如果-则”命题的定理
1.3 其他的证明形式
1.3.1 证明集合等价性
1.3.2 逆否命题
1.3.3 反证法
1.3.4 反例
1.4 归纳证明
1.4.1 整数上的归纳法
1.4.2 更一般形式的整数归纳法
1.4.3 结构归纳法
1.4.4 互归纳法
1.5 自动机理论的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 语言
1.5.4 问题
1.6 小结
1.7 参考文献
第2章 有穷自动机
2.1 有穷自动机的非形式化描述
2.1.1 基本规则
2.1.2 协议
2.1.3 允许自动机忽略动作
2.1.4 整个系统成为一个自动机
2.1.5 用乘积自动机验证协议
2.2 确定型有穷自动机
2.2.1 确定型有穷自动机的定义
2.2.2 DFA如何处理串
2.2.3 DFA的简化记号
2.2.4 把转移函数扩展到串
2.2.5 DFA的语言
2.2.6 习题
2.3 非确定型有穷自动机
2.3.1 非确定型有穷自动机的非形式化观点
2.3.2 非确定型有穷自动机的定义
2.3.3 扩展转移函数
2.3.4 NFA的语言
2.3.5 确定型有穷自动机与非确定型有穷自动机的等价性
2.3.6 子集构造的坏情形
2.3.7 习题
2.4 应用:文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非确定型有穷自动机
2.4.3 识别关键字集合的DFA
2.4.4 习题
2.5 带ε转移的有穷自动机
2.5.1 ε转移的用途
2.5.2 ε-NFA的形式化定义
2.5.3 ε闭包
2.5.4 ε-NFA的扩展转移和语言
2.5.5 消除ε转移
2.5.6 习题
2.6 小结
2.7 参考文献
第3章 正则表达式与正则语言
第4章 正则语言的性质
第5章 上下文无关文法及上下文无关语言
第6章 下推自动机
第7章 上下文无关语言的性质
第8章 图灵机导引第9章不可判定性
第10章 难解问题
第11章 其他问题类
索引
同类热销排行榜
- C语言与程序设计教程(高等学校计算机类十二五规划教材)16
- 电机与拖动基础(教育部高等学校自动化专业教学指导分委员会规划工程应用型自动化专业系列教材)13.48
- 传感器与检测技术(第2版高职高专电子信息类系列教材)13.6
- ASP.NET项目开发实战(高职高专计算机项目任务驱动模式教材)15.2
- Access数据库实用教程(第2版十二五职业教育国家规划教材)14.72
- 信号与系统(第3版下普通高等教育九五国家级重点教材)15.08
- 电气控制与PLC(普通高等教育十二五电气信息类规划教材)17.2
- 数字电子技术基础(第2版)17.36
- VB程序设计及应用(第3版十二五职业教育国家规划教材)14.32
- Java Web从入门到精通(附光盘)/软件开发视频大讲堂27.92
推荐书目
-
孩子你慢慢来/人生三书 华人世界率性犀利的一枝笔,龙应台独家授权《孩子你慢慢来》20周年经典新版。她的《...
-
时间简史(插图版) 相对论、黑洞、弯曲空间……这些词给我们的感觉是艰深、晦涩、难以理解而且与我们的...
-
本质(精) 改革开放40年,恰如一部四部曲的年代大戏。技术突变、产品迭代、产业升级、资本对接...