形式语言与自动机理论 第2版【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

形式语言与自动机理论 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 绪论1

1.1 集合的基础知识2

1.1.1 集合及其表示2

1.1.2 集合之间的关系5

1.1.3 集合的运算6

1.2 关系12

1.2.1 二元关系12

1.2.2 等价关系与等价类13

1.2.3 关系的合成14

1.2.4 递归定义与归纳证明15

1.2.5 关系的闭包18

1.3 图19

1.3.1 无向图19

1.3.2 有向图21

1.3.3 树23

1.4 语言24

1.4.1 什么是语言24

1.4.2 形式语言与自动机理论的产生与作用25

1.4.3 基本概念28

1.5 小结35

习题35

第2章 文法42

2.1 启示43

2.2 形式定义48

2.3 文法的构造58

2.4 文法的乔姆斯基体系68

2.5 空语句79

2.6 小结82

习题82

第3章 有穷状态自动机86

3.1 语言的识别86

3.2 有穷状态自动机89

3.3 不确定的有穷状态自动机102

3.3.1 作为对DFA的修改102

3.3.2 NFA的形式定义104

3.3.3 NFA与DFA等价106

3.4 带空移动的有穷状态自动机110

3.5 FA是正则语言的识别器115

3.5.1 FA与右线性文法115

3.5.2 FA与左线性文法120

3.6 FA的一些变形122

3.6.1 双向有穷状态自动机122

3.6.2 带输出的FA123

3.7 小结125

习题126

第4章 正则表达式131

4.1 启示131

4.2 正则表达式的形式定义133

4.3 正则表达式与FA等价135

4.3.1 正则表达式到FA的等价变换135

4.3.2 正则语言可以用正则表达式表示144

4.4 正则语言等价模型的总结150

4.5 小结152

习题153

第5章 正则语言的性质156

5.1 正则语言的泵引理156

5.2 正则语言的封闭性162

5.3 Myhill-Nerode定理与DFA的极小化170

5.3.1 Myhill-Nerode定理170

5.3.2 DFA的极小化180

5.4 关于正则语言的判定算法189

5.5 小结190

习题191

第6章 上下文无关语言194

6.1 上下文无关文法195

6.1.1 上下文无关文法的派生树195

6.1.2 二义性202

6.1.3 自顶向下的分析和自底向上的分析205

6.2 上下文无关文法的化简207

6.2.1 去无用符号208

6.2.2 去ε-产生式212

6.2.3 去单一产生式组216

6.3 乔姆斯基范式219

6.4 格雷巴赫范式223

6.5 自嵌套文法229

6.6 小结230

习题230

第7章 下推自动机235

7.1 基本定义235

7.2 PDA与CFG等价242

7.2.1 PDA用空栈接受和用终止状态接受等价243

7.2.2 PDA与CFG等价246

7.3 小结257

习题257

第8章 上下文无关语言的性质260

8.1 上下文无关语言的泵引理260

8.2 上下文无关语言的封闭性267

8.3 上下文无关语言的判定算法273

8.3.1 L空否的判定273

8.3.2 L是否有穷的判定274

8.3.3 x是否为L的句子的判定276

8.4 小结278

习题278

第9章 图灵机280

9.1 基本概念281

9.1.1 基本图灵机282

9.1.2 图灵机作为非负整函数的计算模型289

9.1.3 图灵机的构造293

9.2 图灵机的变形300

9.2.1 双向无穷带图灵机300

9.2.2 多带图灵机304

9.2.3 不确定的图灵机306

9.2.4 多维图灵机308

9.2.5 其他图灵机310

9.3 通用图灵机313

9.4 几个相关的概念315

9.4.1 可计算性315

9.4.2 P与NP相关问题316

9.5 小结316

习题317

第10章 上下文有关语言320

10.1 图灵机与短语结构文法的等价性320

10.2 线性有界自动机及其与上下文有关文法的等价性323

10.3 小结325

习题325

附录A 教学设计327

附录B 缩写符号338

词汇索引340

参考文献348