热搜关键词: EMC电机控制PLC数字电路PCB设计

pdf

自动机理论、语言和计算导论 第三版

  • 1星
  • 2023-01-18
  • 70.66MB
  • 需要1积分
  • 1次下载
  • favicon收藏
  • rep举报
  • free评论
标签: 计算机

计算机

本书是关于形式语言、自动机理论和计算面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明,使用图来帮助阐明思想,含了大量的难度各异的示例和以便读者确认和加深对内容的理解。本书已被世界许多有名大学作为计算机理论课程的教材或教学参考书,适合作为高校计算机专业高年级本科生及研究生的教材,还可供从事理论计算工作的研究人员参考。

译者序

前言

第1章  自动机:方法与体验  1

1.1  为什么研究自动机理论  1

1.1.1  有穷自动机简介  1

1.1.2  结构表示法  3

1.1.3  自动机与复杂性  3

1.2  形式化证明简介  3

1.2.1  演绎证明  4

1.2.2  求助于定义  6

1.2.3  其他定理形式  7

1.2.4  表面上不是“如果-则”命题的

定理  9

1.3  其他的证明形式  9

1.3.1  证明集合等价性  9

1.3.2  逆否命题  10

1.3.3  反证法  12

1.3.4  反例  12

1.4  归纳证明  13

1.4.1  整数上的归纳法  13

1.4.2  更一般形式的整数归纳法  16

1.4.3  结构归纳法  16

1.4.4  互归纳法  18

1.5  自动机理论的中心概念  19

1.5.1  字母表  19

1.5.2  串  20

1.5.3  语言  21

1.5.4  问题  21

1.6  小结  23

1.7  参考文献  24

第2章  有穷自动机  25

2.1  有穷自动机的非形式化描述  25

2.1.1  基本规则  26

2.1.2  协议  26

2.1.3  允许自动机忽略动作  27

2.1.4  整个系统成为一个自动机  29

2.1.5  用乘积自动机验证协议  30

2.2  确定型有穷自动机  30

2.2.1  确定型有穷自动机的定义  31

2.2.2  DFA如何处理串  31

2.2.3  DFA的简化记号  32

2.2.4  把转移函数扩展到串  33

2.2.5  DFA的语言  35

2.2.6  35

2.3  非确定型有穷自动机  37

2.3.1  非确定型有穷自动机的非形式化观点  37

2.3.2  非确定型有穷自动机的定义  38

2.3.3  扩展转移函数  39

2.3.4  NFA的语言  39

2.3.5  确定型有穷自动机与非确定型有穷自动机的等价性  40

2.3.6  子集构造的坏情形  43

2.3.7  45

2.4  应用:文本搜索  46

2.4.1  在文本中查找串  46

2.4.2  文本搜索的非确定型有穷自动机  46

2.4.3  识别关键字集合的DFA  47

2.4.4  49

2.5  带e  转移的有穷自动机  49

2.5.1  e  转移的用途  49

2.5.2  e-NFA的形式化定义  50

2.5.3  e  51

2.5.4  e-NFA的扩展转移和语言  52

2.5.5  消除  e  转移  53

2.5.6  54

2.6  小结  55

2.7  参考文献  55

第3章  正则表达式与正则语言  57

3.1  正则表达式  57

3.1.1  正则表达式运算符  57

3.1.2  构造正则表达式  59

3.1.3  正则表达式运算符的优先级  60

3.1.4  61

3.2  有穷自动机和正则表达式  61

3.2.1  从DFA到正则表达式  62

3.2.2  通过消除状态把DFA转化为正则表达式  65

3.2.3  把正则表达式转化为自动机  69

3.2.4  72

3.3  正则表达式的应用  73

3.3.1  UNIX中的正则表达式  73

3.3.2  词法分析  74

3.3.3  查找文本中的模式  76

3.3.4  77

3.4  正则表达式代数定律  77

3.4.1  结合律与交换律  78

3.4.2  单位元与零元  78

3.4.3  分配律  79

3.4.4  幂等律  79

3.4.5  与有关的定律  79

3.4.6  发现正则表达式定律  80

3.4.7  检验正则表达式代数定律  81

3.4.8  82

3.5  小结  83

3.6  参考文献  84

第4章  正则语言的性质  85

4.1  证明语言的非正则性  85

4.1.1  正则语言的泵引理  85

4.1.2  泵引理的应用  87

4.1.3  88

4.2  正则语言的封闭性  89

4.2.1  正则语言在布尔运算下的封闭性  89

4.2.2  反转  93

4.2.3  同态  94

4.2.4  逆同态  96

4.2.5  99

4.3  正则语言的判定性质  102

4.3.1  在各种表示之间转化  102

4.3.2  测试正则语言的空性  104

4.3.3  测试正则语言的成员性  104

4.3.4  105

4.4  自动机的等价性和小化  105

4.4.1  测试状态的等价性  105

4.4.2  测试正则语言的等价性  107

4.4.3  DFA小化  108

4.4.4  为什么不能比小DFA更小  110

4.4.5  111

4.5  小结  112

4.6  参考文献  112

第5章  上下文无关文法及上下文无关语言  115

5.1  上下文无关文法  115

5.1.1  一个非形式化的例子  115

5.1.2  上下文无关文法的定义  116

5.1.3  使用文法来推导  118

5.1.4  左推导和右推导  119

5.1.5  文法的语言  120

5.1.6  句型  121

5.1.7  122

5.2  语法分析树  124

5.2.1  构造语法分析树  124

5.2.2  语法分析树的产生  125

5.2.3  推理、推导和语法分析树  125

5.2.4  从推理到树  126

5.2.5  从树到推导  127

5.2.6  从推导到递归推理  129

5.2.7  131

5.3  上下文无关文法的应用  131

5.3.1  语法分析器  131

5.3.2  语法分析器生成器YACC  133

5.3.3  标记语言  134

5.3.4  XML和文档类型定义  135

5.3.5  140

5.4  文法和语言的歧义性  141

5.4.1  歧义文法  141

5.4.2  去除文法的歧义性  143

5.4.3  左推导作为表达歧义性的一种方式  145

5.4.4  固有的歧义性  146

5.4.5  147

5.5  小结  148

5.6  参考文献  148

第6章  下推自动机  151

6.1  下推自动机的定义  151

6.1.1  非形式化的介绍  151

6.1.2  下推自动机的形式化定义  152

6.1.3  PDA的图形表示  154

6.1.4  PDA的瞬时描述  154

6.1.5  157

6.2  PDA的语言  158

6.2.1  以终结状态方式接受  158

6.2.2  以空栈方式接受  159

6.2.3  从空栈方式到终结状态方式  159

6.2.4  从终结状态方式到空栈方式  162

6.2.5  163

6.3  PDA和CFG的等价性  164

6.3.1  从文法到PDA  164

6.3.2  从PDA到文法  167

6.3.3  170

6.4  确定型PDA  171

6.4.1  确定型PDA的定义  171

6.4.2  正则语言与确定型PDA  172

6.4.3  DPDA与上下文无关语言  173

6.4.4  DPDA与歧义文法  173

6.4.5  174

6.5  小结  175

6.6  参考文献  175

第7章  上下文无关语言的性质  177

7.1  上下文无关文法的范式  177

7.1.1  去除无用的符号  177

7.1.2  计算产生符号和可达符号  179

7.1.3  去除e产生式  180

7.1.4  去除单位产生式  182

7.1.5  乔姆斯基范式  185

7.1.6  189

7.2  上下文无关语言的泵引理  191

7.2.1  语法分析树的大小  191

7.2.2  泵引理的陈述  191

7.2.3  CFL的泵引理的应用  193

7.2.4  195

7.3  上下文无关语言的封闭性  196

7.3.1  代入  196

7.3.2  代入定理的应用  198

7.3.3  反转  198

7.3.4  与正则语言的交  199

7.3.5  逆同态  202

7.3.6  204

7.4  CFL的判定性质  205

7.4.1  在CFG和PDA之间相互转化的复杂性  205

7.4.2  变换到乔姆斯基范式的运行时间  207

7.4.3  测试CFL的空性  207

7.4.4  测试CFL的成员性  209

7.4.5  不可判定的CFL问题一览  211

7.4.6  211

7.5  小结  212

7.6  参考文献  212

第8章  图灵机导引  215

8.1  计算机不能解答的问题  215

8.1.1  显示“hello,  world”的程序  215

8.1.2  假设中的“hello,  world”检验程序  217

8.1.3  把问题归约到另一个问题  219

8.1.4  221

8.2  图灵机  221

8.2.1  寻求判定所有数学问题  222

8.2.2  图灵机的记号  222

8.2.3  图灵机的瞬时描述  223

8.2.4  图灵机转移图  225

8.2.5  图灵机的语言  227

8.2.6  图灵机与停机  228

8.2.7  228

8.3  图灵机的程序设计技术  229

8.3.1  在状态中存储  230

8.3.2  多道  231

8.3.3  子程序  232

8.3.4  234

8.4  基本图灵机的扩展  234

8.4.1  多带图灵机  234

8.4.2  单带图灵机与多带图灵机的等价性  235

8.4.3  运行时间与多带合一构造  236

8.4.4  非确定型图灵机  237

8.4.5  239

8.5  受的图灵机  240

8.5.1  具有半无穷带的图灵机  240

8.5.2  多堆栈机器  242

8.5.3  计数器机器  244

8.5.4  计数器机器的能力  244

8.5.5  246

8.6  图灵机与计算机  247

8.6.1  用计算机模拟图灵机  247

8.6.2  用图灵机模拟计算机  248

8.6.3  比较计算机与图灵机的运行时间  251

8.7  小结  252

8.8  参考文献  253

第9章  不可判定性  255

9.1  非递归可枚举语言  255

9.1.1  枚举制串  256

9.1.2  图灵机编码  256

9.1.3  对角化语言  257

9.1.4  证明Ld  非递归可枚举  258

9.1.5  258

9.2  递归可枚举但不可判定的问题  259

9.2.1  递归语言  259

9.2.2  递归语言和递归可枚举语言的补  260

9.2.3  通用语言  262

9.2.4  通用语言的不可判定性  263

9.2.5  264

9.3  与图灵机有关的不可判定问题  266

9.3.1  归约  266

9.3.2  接受空语言的图灵机  267

9.3.3  莱斯定理与递归可枚举语言的性质  269

9.3.4  与图灵机说明有关的问题  271

9.3.5  272

9.4  波斯特对应问题  272

9.4.1  波斯特对应问题的定义  273

9.4.2  “修改过的”PCP  274

9.4.3  PCP不可判定性证明之完成  276

9.4.4  281

9.5  其他不可判定问题  281

9.5.1  与程序有关的问题  281

9.5.2  CFG歧义性问题  281

9.5.3  表语言的补  283

9.5.4  285

9.6  小结  285

9.7  参考文献  286

第10章  难解问题  289

10.1  P类和NP类  289

10.1.1  可在多项式时间内解答的问题  290

10.1.2  例子:克鲁斯卡尔算法  290

10.1.3  非确定型多项式时间  293

10.1.4  NP例子:货郎问题  293

10.1.5  多项式时间归约  294

10.1.6  NP问题  295

10.1.7  296

10.2  NP问题  297

10.2.1  可满足性问题  297

10.2.2  表示SAT实例  299

10.2.3  SAT问题的NP性  299

10.2.4  304

10.3  约束可满足性问题  304

10.3.1  布尔表达式的范式  304

10.3.2  把表达式转化成CNF  305

10.3.3  CSAT的NP性  308

10.3.4  3SAT的NP性  311

10.3.5  312

10.4  其他的NP问题  312

10.4.1  描述NP问题  313

10.4.2  独立集问题  313

10.4.3  顶点覆盖问题  316

10.4.4  有向哈密顿回路问题  317

10.4.5  无向哈密顿回路与TSP  322

10.4.6  NP问题小结  323

10.4.7  323

10.5  小结  326

10.6  参考文献  326

第11章  其他问题类  329

11.1  NP  中的语言的补  330

11.1.1  NP  补语言类  330

11.1.2  NP问题与  NP  补  330

11.1.3  331

11.2  在多项式空间内可解决的问题  331

11.2.1  多项式空间图灵机  332

11.2.2  PS  和  NPS  与前面定义的类的关系  332

11.2.3  确定型多项式空间与非确定型多项式空间  333

11.3  对  PS  的问题  335

11.3.1  PS性  335

11.3.2  带量词的布尔公式  336

11.3.3  带量词的布尔公式的求值  337

11.3.4  QBF问题的PS性  338

11.3.5  341

11.4  基于随机化的语言类  342

11.4.1  快速排序:随机算法举例  342

11.4.2  随机化的图灵机模型  343

11.4.3  随机化图灵机的语言  344

11.4.4  RP  类  345

11.4.5  识别  RP  语言  347

11.4.6  ZPP  类  348

11.4.7  RP  与  ZPP  之间的关系  348

11.4.8  与  P  类和  NP  类的关系  349

11.5  素数性测试的复杂性  349

11.5.1  素数性测试的重要性  350

11.5.2  同余算术简介  351

11.5.3  同余算术计算的复杂性  352

11.5.4  随机多项式素数性测试  353

11.5.5  非确定型素数性测试  354

11.5.6  356

11.6  小结  356

11.7  参考文献  357

索引  359

推荐帖子 最新更新时间:2023-01-30 02:10

diy效果器 遇到的一些问题请各位指教了啊 多谢
大家好: 这是一张电吉他单块效果器ds1的图纸,有些地方不明太,跟大家请教一下,谢谢了 1:两个虚线框里的ic如何接啊,我知道ic1a,ic1b的解法是原理的中的圈1到圈7,但为什么没有圈1和圈5的地方啊? 2:还有ic2怎么接啊?  ic1和ic2即两个虚线框里的应该是两个方案 3:如果是ic2的方案,那这个ic具体跟圈1到圈7怎么对应啊?我看ic2只标注了自身的管脚还是什么?? 4:
tangchao4587 模拟电子
TI 专家: LM5017 的反相升降压电路支持负电源
如图 1a 和 1b 所示,只需对降压转换器原理图进行简单修改,便可将同步降压转换器 IC 用于反相升降压配置。反相升降压转换器可生成负极输出电压,计算公式如下:VOUT= -D/(1-D) x VIN 反相升降压转换器的工作情况如图 2a 和 2b 所示。在 TON(Q1:导通;Q2:关闭)期间,电感器储存能量;而在 TOFF(Q1:关闭;Q2:导通)期间,电感器为输出电容器充电。
qwqwqw2088 模拟与混合信号
电源管理集成电路 (PMIC) 会是未来的主流方向吗?
灵活、简化的编程流程使设计人员能够将单个 IC 应用于各种用例,从而帮助制造商缩短上市时间,降低物料成本。 电源管理集成电路 (PMIC) 是智能手表、恒温器、耳机、平板电脑、固态硬盘、电池充电器、视频摄像头等多种设备的重要组件。Qorvo 的可定制 PMIC 为系统设计人员提供了常规电源设备的一种替代方案,同时具有敏捷性和设计灵活性,能够适应各种应用和广泛的市场需求。 看来,电源管理
alan000345 RF/无线
DSP并行FLASH引导的一点经验
前几天自制的DSP板引导成功,早就打算写写这方面的东西。我用的DSP是 5416,以其为核心,做了一个相对独立的子系统(硬件、软件、算法),目前都已基本做好。下面把在FLASH引导方面做的工作向大家汇报一下,希望能对大家有所帮助。本人经验和文笔都有限,写的不好请大家谅解。 硬件环境: DSP:TMS320VC5416PGE160 FLASH:SST39VF400A-70-4C-EK 都是贴片的
fish001 DSP 与 ARM 处理器
旧手机别卖掉换脸盆了,自制服务器了解一下!
来源:csdn 本文将向你展示如何使用 UrBackup 和 Linux Deploy在一台 Android 旧手机上搭建一台备份服务器。旧手机的污染问题众所周知,我有一台旧手机,虽然外壳有裂纹和磨损,但性能还很好,因此我打算废物再利用一下。 你的旧手机很可能: 并没有那么旧(你会像换手机那样一两年就换一台电脑吗?) 有 4-8 个处理器和大约
eric_wang DIY/开源硬件专区
【 XMC4800 Relax EtherCAT Kit测评】+freertos实时系统使用
本帖最后由 anger0925 于 2019-1-7 14:23 编辑 在MCU的应用中,有一个实时系统,处理任务比较方便。Freertos实时系统移植应用都比较简单方便。在DAVE的应用中看到已经有freertos。DAVE集成开发环境比较强大,把各种可能用到的模块都已经实现,让应用开发者不花时间在freertos等模块上,能节省很多时间来专门部署自己的应用。1,在DAVE中添加freert
anger0925 工控电子
更加智能:智能电池电量计如何有效改进动态血糖监视仪的电池使用寿命
人体血糖值的偏高或偏低都有可能导致严重的健康威胁,因此监测血糖水平是重中之重。目前全球已有1.5亿人口罹患糖尿病,所以个人便携型血糖监测仪(BGM)的需求巨大。 图1所示的动态血糖监测仪(CGM),可帮助糖尿病患者实时检查血糖读数,也可在超长时间段内监测血糖值。CGM能够持续监测血糖水平,然后在用户血糖值达到危险值时提示用户。这款监测仪通常包含图2所示的传感器单元和图3所示的聚合器单元。
alan000345 TI技术论坛
软件工程读书笔记第一章-软件工程导论
1、试图为软件工程寻求通用的符号系统、方法和技术是毫无意义的 2、软件失败两方面原因:不断增长的需求、期望值太低 3、软件工程的目的是支持专业化的软件开发个体编程 4、软件包括程序和所有使程序正确运行所需要的相关文档和配置信息 5、通用软件产品和定制软件产品重要区别在于通用软件产品中,软件描述由开发者自己完成,而定制软件产品,其软件描述通常由客户给出,开发者必须按照客户要求进行开发。两类的
白丁 编程基础

评论

G886
了解了解,谢谢分享!
2023-01-28 11:22:45
登录/注册

意见反馈

求资源

回顶部
查找数据手册?

EEWorld Datasheet 技术支持

热门活动

相关视频

可能感兴趣器件

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版 版权声明

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2022 EEWORLD.com.cn, Inc. All rights reserved
×