自动机理论、语言和计算导论

封面
书名
版权
前言
目录
第1章  自动机：方法与体验
为什么研究自动机理论
有穷自动机简介
结构表示法
自动机与复杂性
形式化证明简介
演绎证明
求助于定义
其他定理形式
表面上不是“如果-则”命题的定理
其他的证明形式
证明集合等价性
逆否命题
反证法
反例
归纳证明
整数上的归纳法
更一般形式的整数归纳法
结构归纳法
互归纳法
自动机理论的中心概念
字母表
串
语言
问题
小结
参考文献
第2章  有穷自动机
有穷自动机的非形式化描述
基本规则
协议
允许自动机忽略动作
整个系统成为一个自动机
用乘积自动机验证协议
确定型有穷自动机
确定型有穷自动机的定义
DFA如何处理串
DFA的简化记号
把转移函数扩展到串
DFA的语言
习题
非确定型有穷自动机
非确定型有穷自动机的非形式化观点
非确定型有穷自动机的定义
扩展转移函数
NFA的语言
确定型有穷自动机与非确定型有穷自动机的等价性
子集构造的坏情形
习题
应用：文本搜索
在文本中查找串
文本搜索的非确定型有穷自动机
识别关键字集合的DFA
习题
带ε转移的有穷自动机
ε转移的用途
ε-NFA的形式化定义
ε闭包
ε-NFA的扩展转移和语言
消除ε转移
习题
小结
参考文献
第3章  正则表达式与正则语言
正则表达式
正则表达式运算符
构造正则表达式
正则表达式运算符的优先级
习题
有穷自动机和正则表达式
从DFA到正则表达式
通过消除状态把DFA转化为正则表达式
把正则表达式转化为自动机
习题
正则表达式的应用
UNIX中的正则表达式
词法分析
查找文本中的模式
习题
正则表达式代数定律
结合律与交换律
单位元与零元
分配律
幂等律
与闭包有关的定律
发现正则表达式定律
检验正则表达式代数定律
习题
小结
参考文献
第4章  正则语言的性质
证明语言的非正则性
正则语言的泵引理
泵引理的应用
习题
正则语言的封闭性
正则语言在布尔运算下的封闭性
反转
同态
逆同态
习题
正则语言的判定性质
在各种表示之间转化
测试正则语言的空性
测试正则语言的成员性
习题
自动机的等价性和最小化
测试状态的等价性
测试正则语言的等价性
DFA最小化
为什么不能比最小DFA更小
习题
小结
参考文献
第5章  上下文无关文法及上下文无关语言
上下文无关文法
一个非形式化的例子
上下文无关文法的定义
使用文法来推导
最左推导和最右推导
文法的语言
句型
习题
语法分析树
构造语法分析树
语法分析树的产生
推理、推导和语法分析树
从推理到树
从树到推导
从推导到递归推理
习题
上下文无关文法的应用
语法分析器
语法分析器生成器YACC
标记语言
XML和文档类型定义
习题
文法和语言的歧义性
歧义文法
去除文法的歧义性
最左推导作为表达歧义性的一种方式
固有的歧义性
习题
小结
参考文献
第6章  下推自动机
下推自动机的定义
非形式化的介绍
下推自动机的形式化定义
PDA的图形表示
PDA的瞬时描述
习题
PDA的语言
以终结状态方式接受
以空栈方式接受
从空栈方式到终结状态方式
从终结状态方式到空栈方式
习题
PDA和CFG的等价性
从文法到PDA
从PDA到文法
习题
确定型PDA
确定型PDA的定义
正则语言与确定型PDA
DPDA与上下文无关语言
DPDA与歧义文法
习题
小结
参考文献
第7章  上下文无关语言的性质
上下文无关文法的范式
去除无用的符号
计算产生符号和可达符号
去除ε产生式
去除单位产生式
乔姆斯基范式
习题
上下文无关语言的泵引理
语法分析树的大小
泵引理的陈述
CFL的泵引理的应用
习题
上下文无关语言的封闭性
代入
代入定理的应用
反转
与正则语言的交
逆同态
习题
CFL的判定性质
在CFG和PDA之间互相转化的复杂性
变换到乔姆斯基范式的运行时间
测试CFL的空性
测试CFL的成员性
不可判定的CFL问题一览
习题
小结
参考文献
第8章  图灵机导引
计算机不能解答的问题
显示“hello,world”的程序
假设中的“hello,world”检验程序
把问题归约到另一个问题
习题
图灵机
寻求判定所有数学问题
图灵机的记号
图灵机的瞬时描述
图灵机转移图
图灵机的语言
图灵机与停机
习题
图灵机的程序设计技术
在状态中存储
多道
子程序
习题
基本图灵机的扩展
多带图灵机
单带图灵机与多带图灵机的等价性
运行时间与多带合一构造
非确定型图灵机
习题
受限制的图灵机
具有半无穷带的图灵机
多堆栈机器
计数器机器
计数器机器的能力
习题
图灵机与计算机
用计算机模拟图灵机
用图灵机模拟计算机
比较计算机与图灵机的运行时间
小结
参考文献
第9章  不可判定性
非递归可枚举语言
枚举二进制串
图灵机编码
对角化语言
证明Ld非递归可枚举
习题
是递归可枚举但不可判定的问题
递归语言
递归语言和递归可枚举语言的补
通用语言
通用语言的不可判定性
习题
与图灵机有关的不可判定问题
归约
接受空语言的图灵机
莱斯定理与递归可枚举语言的性质
与图灵机说明有关的问题
习题
波斯特对应问题
波斯特对应问题的定义
“修改过的”PCP
PCP不可判定性证明之完成
习题
其他不可判定问题
与程序有关的问题
CFG歧义性问题
表语言的补
习题
小结
参考文献
第10章  难解问题
P类和NP类
可在多项式时间内解答的问题
例子：克鲁斯卡尔算法
非确定型多项式时间
NP例子：货郎问题
多项式时间归约
NP完全问题
习题
NP完全问题
可满足性问题
表示SAT实例
SAT问题的NP完全性
习题
约束可满足性问题
布尔表达式的范式
把表达式转化成CNF
CSAT的NP完全性
3SAT的NP完全性
习题
其他的NP完全问题
描述NP完全问题
独立集问题
顶点覆盖问题
有向哈密顿回路问题
无向哈密顿回路与TSP
NP完全问题小结
习题
小结
参考文献
第11章  其他问题类
NP中的语言的补
Np补语言类
NP完全问题与Np补
习题
在多项式空间内可解决的问题
多项式空间图灵机
ps和Nps与前面定义的类的关系
确定型多项式空间与非确定型多项式空间
对ps完全的问题
PS完全性
带量词的布尔公式
带量词的布尔公式的求值
QBF问题的PS完全性
习题
基于随机化的语言类
快速排序：随机算法举例
随机化的图灵机模型
随机化图灵机的语言
Rp类
识别Rp语言
Zpp类
Rp与Zpp之间的关系
与p类和Np类的关系
素数性测试的复杂性
素数性测试的重要性
同余算术简介
同余算术计算的复杂性
随机多项式素数性测试
非确定型素数性测试
习题
小结
参考文献
索引