语言与机器计算机科学理论导论 原书第3版PDF电子书下载

第一部分　基础 2

第1章 数学预备知识 2

1.1　集合论 2

1.2　笛卡儿积、关系和函数 4

1.3　等价关系 6

1.4　可数集合和不可数集合 7

1.5　对角化和自反 9

1.6　递归定义 11

1.7　数学归纳 13

1.8　有向图 15

1.9　练习 18

参考文献注释 20

第2章 语言 21

2.1　字符串和语言 21

2.2　语言的有穷规格说明 23

2.3　正则集合和表达式 25

2.4　正则表达式和文本搜索 28

2.5　练习 30

参考文献注释 32

第二部分　文法、自动机和语言第3章 上下文无关文法 34

3.1　上下文无关文法和语言 36

3.2　文法和语言的例子 41

3.3　正则文法 44

3.4　验证文法 45

3.5　最左推导和二义性 48

3.6　上下文无关文法和编程语言定义 51

3.7　练习 53

参考文献注释 56

第4章 上下文无关文法范式 57

4.1　文法转换 57

4.2　消去λ规则 58

4.3　去掉链规则 62

4.4　无用符 64

4.5　乔姆斯基范式 67

4.6　CYK算法 69

4.7　去掉直接左递归 71

4.8　格立巴赫范式 73

4.9　练习 77

参考文献注释 80

第5章 有限自动机 81

5.1　一个有限状态自动机 81

5.2　确定型有限自动机 82

5.3　状态图和例子 84

5.4　非确定型有限自动机 88

5.5　λ-转换 91

5.6　去掉非确定性 94

5.7　DFA的最小化 99

5.8　练习 103

参考文献注释 107

第6章 正则语言的性质 108

6.1　有限状态机接收正则语言 108

6.2　表达式图 109

6.3　正则文法和有限自动机 111

6.4　正则语言的封闭性质 114

6.5　非正则语言 115

6.6　规则语言的泵引理 116

6.7　Myhill-Nerode定理 119

6.8　练习 122

参考文献注释 125

第7章 下推自动机和上下文无关语言 126

7.1　下推自动机 126

7.2　PDA的变种 129

7.3　上下文无关语言的接收 132

7.4　上下文无关语言的泵引理 136

7.5　上下文无关语言的封闭性 138

7.6　练习 140

参考文献注释 143

第三部分　可计算性第8章 图灵机 146

8.1　标准图灵机 146

8.2　作为语言接收器的图灵机 148

8.3　可供选择接收标准 150

8.4　多道图灵机 151

8.5　双向图灵机 151

8.6　多带图灵机 153

8.7　非确定型图灵机 157

8.8　用来枚举语言的图灵机 162

8.9　练习 166

参考文献注释 169

第9章 图灵可计算函数 170

9.1　函数的计算 170

9.2　数值计算 172

9.3　图灵机的顺序操作 174

9.4　函数的合成 178

9.5　不可计算函数 180

9.6　关于编程语言 181

9.7　练习 184

参考文献注释 186

第10章 乔姆斯基层次 187

10.1　无限制文法 187

10.2　上下文有关文法 191

10.3　线性有界自动机 192

10.4　乔姆斯基层次 195

10.5　练习 195

参考文献注释 197

第11章 判定问题与丘奇—图灵论题 198

11.1　判定问题的描述 198

11.2　判定问题和递归语言 199

11.3　问题归约 201

11.4　丘奇—图灵论题 203

11.5　通用机 204

11.6　练习 207

参考文献注释 208

第12章 不可判定性 209

12.1 图灵机的停机问题 209

12.2　问题归约和不可判定性 211

12.3　其他的停机问题 213

12.4　莱斯定理 215

12.5　不可解决的词问题 216

12.6　波斯特对应问题 218

12.7　上下文无关文法中的不可判定问题 221

12.8　练习 223

参考文献注释 225

第13章　Mu-递归函数 226

13.1　原始递归函数 226

13.2　一些原始递归函数 228

13.3　有界操作符 230

13.4　除法函数 234

13.5　歌德尔数字和串值递归 235

13.6　可计算部分函数 237

13.7　图灵可计算函数和Mu-递归函数 240

13.8　修订的丘奇—图灵论题 243

13.9　练习 245

参考文献注释 249

第四部分　计算复杂性第14章 时间复杂性 252

14.1　复杂性度量 252

14.2　增长的速度 253

14.3　图灵机的时间复杂性 256

14.4　复杂性和图灵机的变种 259

14.5　线性加速 260

14.6　语言时间复杂性的属性 262

14.7　计算机计算的模拟 266

14.8　练习 268

参考文献注释 270

第15章 P、NP和库克定理 271

15.1 非确定型图灵机的时间复杂性 271

15.2　P类和NP类 272

15.3　问题表示和复杂性 273

15.4　判定问题和复杂性类 275

15.5　哈密尔顿回路问题 276

15.6　多项式时间归约 278

15.7　P=NP? 279

15.8　可满足性问题 280

15.9　复杂类的关系 287

15.10　练习 287

参考文献注释 289

第16章 NP-完全问题 290

16.1 归约和NP-完全问题 290

16.2　三元可满足性问题 291

16.3　三元可满足性的归约 292

16.4　归约和子问题 299

16.5　最优化问题 302

16.6　近似算法 303

16.7　近似方案 305

16.8　练习 307

参考文献注释 308

第17章 其他复杂性类 309

17.1　派生的复杂性类 309

17.2　空间复杂性 310

17.3　空间复杂性和时间复杂性的关系 312

17.4　P-空间，NP-空间和萨维奇定理 315

17.5　P-空间完全性 318

17.6　一个难解问题 320

17.7　练习 321

参考文献注释 321

第五部分　确定型语法分析第18章　语法分析引论 324

18.1　文法图 324

18.2　自顶向下语法分析 325

18.3　归约和自底向上语法分析 328

18.4　自底向上语法分析器 329

18.5　语法分析和编译 331

18.6　练习 332

参考文献注释 333

第19章 LL（k）文法 334

19.1　上下文无关文法中的预读 334

19.2　FIRST集合、FOLLOW集合和预读集合 336

19.3　强LL（k）语法 338

19.4　FIRSTk集合的构造 339

19.5　FOLLOWk集合的构造 341

19.6　强LL（1）文法 342

19.7　强LL（k）分析器 344

19.8　LL（k）文法 345

19.9　练习 346

参考文献注释 348

第20章 LR（k）文法 349

20.1　LR（0）上下文 349

20.2　LR（0）分析器 351

20.3　LR（0）机 352

20.4　被LR（0）机接收 356

20.5　LR（1）文法 360

20.6　练习 365

参考文献注释 366

附录Ⅰ 标记索引 367

附录Ⅱ 希腊字母表 370

附录Ⅲ ASCⅡ字符集 371

附录Ⅳ Java的BNF范式定义 372

参考文献 379

索引 384