语言与机器计算机科学理论导论 原书第3版【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

语言与机器计算机科学理论导论 原书第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