Kamala Krithivasan、Rama R所著的《形式语言，自动机理论与计算导论》用简洁清晰的方式阐述了相关理论概念，并深入涵盖了形式文法及基本的自动机类型。同时对该领域的当前研究趋势进行了相关概述。《形式语言，自动机理论与计算导论》概括了本学科的广泛应用以及关于计算方面的基本定理和原理，对计算机科学与信息技术的本科课程教学具有一定价值。

《形式语言，自动机理论与计算导论》特点：运用大量例题来帮助读者理解概念要点；通过图灵机详尽阐述了可计算性和可判定性问题；提出一些有助于学生进行深入研究的形式语言前沿问题及最新的计算模型；设计多项选择题以帮助学生理解基础理论。

Kamala Krithivasan、Rama R所著的《形式语言，自动机理论与计算导论》主要介绍形式语言、自动机理论及可计算性，主要内容包括：本学科的基础知识、文法、有限状态自动机理论、有限状态自动机变形、下推自动机、图灵机和可计算理论、复杂性原理、时空复杂度、NP完全问题、DNA计算、膜计算以及本学科一些前沿理论等。全书包含大量的例子和图表，便于读者对定义、定理的理解。最后，由浅入深地给出了两套选择题并附有答案，方便教学。

《形式语言，自动机理论与计算导论》适合作为计算机专业高年级本科生或研究生计算理论课程的教材和参考书，也可作为计算机研究人员的参考书。

第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