形式语言，自动机理论与计算导论

内容概要

作者：(印度)卡马拉(Kamala Krithivasan) (印度)拉玛(Rama R) 译者：孟宇龙 李健利 王宇华 合著者：冯晓宁

卡马拉，Kamala Krithivasan，马德拉斯大学博士，1975年进入印度理工学院马德拉斯分校( IIMT)参加工作。计算机科学与工程学院教授，1992-1995年担任院长，在IIMT有着30余年的教学和研究经验。她的研究方向包括形式语言理论、非传统模型计算(如DNA计算)、膜计算以及离散分层计算等。Kamala教授是1986年福尔布莱特学术奖金的获得者，同时还是印度国家工程学会的会员。

Rama R，1989年在安娜大学获得博士学位。进入印度理工学院马德拉斯分校(IIMT)担任副教授之前，

曾在安娜大学工程学院任教。2006年晋职为教授并任教至今。Rama教授拥有20余年的教学和研究经验，并且指导过四位研究生的博士论文。她的研究领域是形式语言与自动机和自然计算。同时，她也是印度工业教育学会的终身会员。

书籍目录

第1章 基础知识1

1.1 集合,关系和函数1

1.2 证明方法4

1.3 图6

1.4 语言:基本概念7

问题与解答10

习题12

第2章 文法14

2.1 文法的定义和分类15

2.2 二义性24

2.3 CFG的化简28

2.4 范式31

问题和解答36

习题39

第3章 有限状态自动机44

3.1 确定有限状态自动机(DFSA)45

3.2 不确定有限状态自动机(NFSA)47

3.3 正则表达式51

问题与解答56

习题61

第4章 有限自动机:特征、性质和可判定性65

4.1 有限自动机和正则文法65

4.2 正则集的泵浦引理66

4.3 封闭性68

4.4 可判定性定理70

问题和解答71

习题71

第5章 带输出的有限状态自动机及其最小化73

5.1 Myhill鄄Nerode定理73

5.2 带输出的有限自动机77

问题与解答79

习题81

第6章 有限自动机的变形83

6.1 双向有限自动机83

6.2 多头有限状态自动机88

6.3 概率有限自动机89

6.4 加权有限自动机和数字图像92

问题与解答105

习题108

第7章 下推自动机110

7.1 下推自动机110

7.2 空栈接受和终态接受的等价113

7.3 CFG和PDA的等价114

问题与解答121

习题124

第8章 上下文无关文法性质与分析126

8.1 CFL的泵引理126

8.2 CFL的封闭性127

8.3 CFL的判定性质130

8.4 CFL的子群132

8.5 帕里克映射与帕里克定理134

8.6 自嵌入性138

8.7 同态下的特性139

问题与解答141

习题144

第9章 图灵机147

9.1 作为接受器的图灵机148

9.2 作为计算设备的图灵机157

9.3 图灵机的构造技术164

问题与解答168

习题172

第10章 图灵机的变形175

10.1 通用版本175

10.2 受限图灵机179

10.3 作为枚举器的图灵机181

10.4 图灵机和0型语言的等价182

10.5 线性有界自动机183

10.6 歌德尔编号184

问题与解答185

习题187

第11章 通用图灵机及可判定性189

11.1 图灵机的编码和枚举189

11.2 递归和递归可枚举集189

11.3 通用图灵机192

11.4 问题,实例和语言195

11.5 莱斯定理195

11.6 规约问题以证明不可判定性197

11.7 波斯特对应问题198

11.8 可计算函数204

问题与解答208

习题209

第12章 时间与空间复杂度211

12.1 RAM模型211

12.2 图灵机的时间与带复杂度214

问题与解答228

习题232

第13章 最近的趋势及应用233

13.1 正则重写233

13.2 马库斯上下文文法241

13.3 林登麦伊尔系统248

13.4 文法系统及分布式自动机256

第14章 一些新的计算模型273

14.1 DNA计算273

14.2 膜计算282

单项选择题(I)296

答案303

单项选择题(II)304

答案311

参考文献312

作者简介

《形式语言,自动机理论与计算导论》用简洁清晰的方式阐述了相关理论概念，并深入涵盖了形式文法及基本的自动机类型。同时对该领域的当前研究趋势进行了相关概述。《形式语言,自动机理论与计算导论》概括了本学科的广泛应用以及关于计算方面的基本定理和原理，对计算机科学与信息技术的本科课程教学具有一定价值。《形式语言,自动机理论与计算导论》特点运用大量例题来帮助读者理解概念要点通过图灵机详尽阐述了可计算性和可判定性问题提出一些有助于学生进行深入研究的形式语言前沿问题及最新的计算模型设计多项选择题以帮助学生理解基础理论。

 形式语言，自动机理论与计算导论下载