形式语言与自动机导论

✍ Scribed by 林兹

• Publisher: 机械工业出版社
• Year: 2005
• Tongue: Chinese
• Leaves: 301
• Series: 计算机科学丛书
• Category: Library

✦ Synopsis

书签已装载，
书签制作方法请找 [email protected]
完全免费

本书是理论计算机科学方面的优秀教材，主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解；本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。　　本书主要介绍形式语言、自动机、可计算性和相关内容。主要内容包括：计算理论导引、有穷自动机、正则语言与正则文法、上下文无关语言及文法、下推自动机、图灵机、形式语言和自动机的层次结构、计算复杂性等。每节后面都给出了习题，并包含部分习题的解答，方便教学。　　本书是理论计算机科学方面的优秀教材之一，可作为高等院校计算机专业的教材，也可作为计算机系统研发人员的参考书。

✦ Table of Contents

封面
书名
版权
前言
目录
目录
出版者的话
专家指导委员会
译者序
前言
第1章　计算理论导引
1 1　数学预备知识和表示
1 1 1　集合
1 1 2　函数和关系
1 1 3　图和树
1 1 4　证明方法
1 2 三个基本概念
1 2 1　语言
1 2 2　文法
1 2 3　自动机
1 3 一些应用＊
2 1 1　确定型接受器和转换图
第2章 有穷自动机
2 1　确定型有穷接受器
2 1 2　语言和dfa对应的语言
2 1 3　正则语言
2 2　非确定型有穷接受器
2 2 1　非确定型接受器的定义
2 2 2　为什么需要非确定型
2 3　确定型有穷接受器和非确定型有穷接受器的等价性
2 4　减少有穷自动机中状态的化简＊
第3章　正则语言与正则文法
3 1　正则表达式
3 1 1　正则表达式的形式化定义
3 1 2　和正则表达式相关的语言
3 2　正则表达式和正则语言之间的联系
3 2 1　正则表达式表示正则语言
3 2 2　正则语言的正则表达式
3 2 3　描述简单模式的正则表达式
3 3　正则文法
3 3 1　右线性文法和左线性文法
3 3 2　右线性文法生成正则语言
3 3 3　正则语言的右线性文法
3 3 4　正则语言和正则文法的等价性
第4章　正则语言的性质
4 1　正则语言的封闭性质
4 1 1　简单集合运算的封闭性
4 1 2　其他运算的封闭性
4 2　正则语言的基本问题
4 3　识别非正则语言
4 3 1　使用鸽巢原理
4 3 2　泵引理
第5章　上下文无关语言
5 1　上下文无关文法
5 1 1 上下文无关语言的例子
5 1 2 最左推导和最右推导
5 1 3　推导树
5 1 4　句型和推导树之间的关系
5 2　分析和二义性
5 2 1　分析和成员资格判定
5 2 2　文法和语言的二义性
5 3　上下文无关文法和程序设计语言
6 1　文法变换方法
6 1 1　一个有用的代入规则
第6章　上下文无关文法的化简与范式
6 1 2　删除无用产生式
6 1 3　消除λ产生式
6 1 4　消除单位产生式
6 2　两个重要的范式
6 2 1　乔姆斯基范式
6 2 2　格里巴克范式
6 3　上下文无关文法的成员资格
判定算法＊
7 1　非确定型下推自动机
第7章 下推自动机
7 1 1　下推自动机的定义
7 1 2　下推自动机接受的语言
7 2　下推自动机与上下文无关语言
7 2 1　上下文无关语言相应的下推自动机
7 2 2　下推自动机相应的上下文无关文法
7 3　确定型下推自动机和确定型上下文无关语言
7 4　确定型上下文无关语言的文法＊
第8章　上下文无关语言的性质
8 1　两个泵引理
8 1 1　上下文无关语言的泵引理
8 1 2　线性语言的泵引理
8 2　上下文无关语言的封闭性质和判定算法
8 2 1　上下文无关语言的封闭性质
8 2 2　上下文无关语言的可判定性质
9 1　标准图灵机
9 1 1　图灵机的定义
第9章　图灵机
9 1 2　作为语言接受器的图灵机
9 1 3　作为转换器的图灵机
9 2　完成复杂任务的组合图灵机
9 3　图灵论题
第10章　图灵机的其他模型
10 1　对图灵机的较小修改
10 1 1　自动机类的等价性
10 1 2 带不动选择的图灵机
10 1 3　单向无穷带图灵机
10 1 4　离线图灵机
10 2　具有更复杂存储的图灵机
10 2 1　多带图灵机
10 2 2　多维图灵机
10 3　非确定型图灵机
10 4　通用图灵机
10 5　线性有界自动机
11 1　递归语言和递归可枚举语言
第11章　形式语言和自动机的层次结构
11 1 1　非递归可枚举的语言
11 1 2　非递归可枚举语言
11 1 3　递归可枚举但非递归的语言
11 2　无限制文法
11 3　上下文相关文法和语言
11 3 1　上下文相关语言和线性有界自动机
11 3 2　递归语言和上下文相关语言的关系
11 4 乔姆斯基层次结构
第12章　算法计算的限制
12 1　图灵机所不能解决的问题
12 1 1　可计算性和可判定性
12 1 2　图灵机停机问题
12 1 3　将一个不可判定问题简化成另外一个问题
12 2　递归可枚举语言的不可判定问题
12 3　波斯特对应问题
12 4　上下文无关语言的不可判定问题
第13章 其他的计算模型
13 1　递归函数
13 1 1　原始递归函数
13 1 2　Ackermann函数
13 1 3　μ递归函数
13 2　波斯特系统
13 3　重写系统
13 3 1　矩阵文法
13 3 2　马尔科夫算法
13 3 3 L系统
第14章 计算复杂性介绍
14 1　计算的效率
14 2　图灵机和复杂性
14 3　语言族和复杂性类
14 4　复杂性类P和NP
部分习题的解答和提示
参考文献
索引