有限自动机理论

1 (p1): 第1章 基础知识
3 (p1-1): 1.1 集合及其运算
5 (p1-2): 1.2 关系
5 (p1-2-1): 1.2.1 二元关系
5 (p1-2-2): 1.2.2 等价关系
6 (p1-2-3): 1.2.3 关系的合成
7 (p1-3): 1.3 证明和证明的方法
7 (p1-3-1): 1.3.1 反证法
8 (p1-3-2): 1.3.2 归纳法
8 (p1-3-3): 1.3.3 递归的定义与归纳证明
9 (p1-4): 1.4 图与树
10 (p1-5): 1.5 语言
10 (p1-6): 1.6 常用术语
13 (p1-7): 1.7 形式语言与自动机的发展
14 (p1-8): 习题1
16 (p2): 第2章 形式语言简介
16 (p2-1): 2.1 例子语言
21 (p2-2): 2.2 文法和语言的关系
21 (p2-2-1): 2.2.1 文法
23 (p2-2-2): 2.2.2 语言
24 (p2-2-3): 2.2.3 文法和语言的3类问题
25 (p2-3): 2.3 Chomsky对文法和语言的分类
30 (p2-4): 2.4 文法产生语言
38 (p2-5): 2.5 无用非终结符
39 (p2-6): 2.6 推导树
41 (p2-7): 2.7 空串定理
42 (p2-8): 2.8 消除左递归
42 (p2-8-1): 2.8.1 消除直接左递归
43 (p2-8-2): 2.8.2 消除间接左递归
45 (p2-9): 2.9 上下文无关文法的另一种表示
46 (p2-10): 2.10 语言之间的运算及运算的封闭性
46 (p2-10-1): 2.10.1 语言之间的基本运算
47 (p2-10-2): 2.10.2 语言之间的运算的封闭性
52 (p2-10-3): 2.10.3 语言之间的其他运算
54 (p2-11): 2.11 正则表达式和正则集
56 (p2-12): 习题2
59 (p3): 第3章 有限状态自动机
59 (p3-1): 3.1 有限状态自动机
61 (p3-2): 3.2 确定的有限状态自动机接收的语言
66 (p3-3): 3.3 确定的有限状态自动机接收语言的例子
78 (p3-4): 3.4 不确定的有限状态自动机
78 (p3-4-1): 3.4.1 不确定的有限状态自动机
80 (p3-4-2): 3.4.2 不确定的有限状态自动机的确定化
85 (p3-5): 3.5 带有ε动作的有限状态自动机
92 (p3-6): 3.6 有限状态自动机的一些变形
92 (p3-6-1): 3.6.1 双向的有限状态自动机
93 (p3-6-2): 3.6.2 带有输出的有限状态自动机
97 (p3-7): 3.7 有限状态接收机的存储技术
99 (p3-8): 3.8 有限状态自动机应用实例
111 (p3-9): 习题3
112 (p4): 第4章 正则语言
112 (p4-1): 4.1 正则语言与有限状态自动机
112 (p4-1-1): 4.1.1 正则表达式对应有限状态自动机
122 (p4-1-2): 4.1.2 正则语言的等价模型
124 (p4-2): 4.2 正则语言的泵浦引理
130 (p4-3): 4.3 正则语言类中的判定算法
132 (p4-4): 习题4
134 (p5): 第5章 下推自动机
134 (p5-1): 5.1 下推自动机
135 (p5-1-1): 5.1.1 确定的下推自动机
138 (p5-1-2): 5.1.2 不确定的下推自动机
140 (p5-1-3): 5.1.3 下推自动机接收语言的两种方式
144 (p5-1-4): 5.1.4 广义下推自动机和单态下推自动机
146 (p5-2): 5.2 上下文无关文法和范式
147 (p5-2-1): 5.2.1 Chomsky范式
148 (p5-2-2): 5.2.2 Greibach范式
150 (p5-3): 5.3 下推自动机与上下文无关语言
162 (p5-4): 5.4 下推自动机应用实例
164 (p5-5): 习题5
166 (p6): 第6章 图灵机
166 (p6-1): 6.1 图灵机的基本模型
166 (p6-1-1): 6.1.1 图灵机的定义
169 (p6-1-2): 6.1.2 图灵机的构造
174 (p6-2): 6.2 图灵机作为非负整数函数计算模型
177 (p6-3): 6.3 图灵机的构造技术
178 (p6-3-1): 6.3.1 图灵机的存储技术
181 (p6-3-2): 6.3.2 图灵机的移动技术
183 (p6-3-3): 6.3.3 图灵机扫描多个符号技术
194…