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 带e 转移的有穷自动机
2.5.1 e 转移的用途
2.5.2 e-NFA的形式化定义
2.5.3 e 闭包
2.5.4 e-NFA的扩展转移和语言
2.5.5 消除 e 转移
2.5.6 习题
2.6 小结
2.7 参考文献
第3章 正则表达式与正则语言
3.1 正则表达式
3.1.1 正则表达式运算符
3.1.2 构造正则表达式
3.1.3 正则表达式运算符的优先级
3.1.4 习题
3.2 有穷自动机和正则表达式
3.2.1 从DFA到正则表达式
3.2.2 通过消除状态把DFA转化为正则表达式
3.2.3 把正则表达式转化为自动机
3.2.4 习题
3.3 正则表达式的应用
3.3.1 UNIX中的正则表达式
3.3.2 词法分析
3.3.3 查找文本中的模式
3.3.4 习题
3.4 正则表达式代数定律
3.4.1 结合律与交换律
3.4.2 单位元与零元
3.4.3 分配律
3.4.4 幂等律
3.4.5 与闭包有关的定律
3.4.6 发现正则表达式定律
3.4.7 检验正则表达式代数定律
3.4.8 习题
3.5 小结
3.6 参考文献
第4章 正则语言的性质
第5章 上下文无关文法及上下文无关语言
第6章 下推自动机
第7章 上下文无关语言的性质
第8章 图灵机导引
第9章 不可判定性
第10章 难解问题
第11章 其他问题类
索引
