形式语言，自动机理论与计算导论
2012-2
电子工业出版社
卡马拉(Kamala Krithivasan),拉玛(Rama R)
328
冯晓宁,孟宇龙,李健利,王宇华
无
形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其多年来在大学讲授该门课程的经验和体会，选择和组织有关内容撰写而成。不仅含有有关正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识，更涉及到本学科方法论中所包含的3个学科形态。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性，从而培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。
作者：(印度)卡马拉(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.2 证明方法
1.3 图
1.4 语言：基本概念
问题与解答
习题
第2章 文法
2.1 文法的定义和分类
2.2 二义性
2.3 CFG 的化简
2.4 范式
问题和解答
习题
第3章 有限状态自动机
3.1 确定有限状态自动机(DFSA)
3.2 不确定有限状态自动机(NFSA)
3.3 正则表达式
问题与解答
习题
第4章 有限自动机：特征、性质和可判定性
4.1 有限自动机和正则文法
4.2 正则集的泵浦引理
4.3 封闭性
4.4 可判定性定理
问题和解答
习题
第5章 带输出的有限状态自动机及其最小化
5.1 Myhill鄄Nerode 定理
5.2 带输出的有限自动机
问题与解答
习题
第6章 有限自动机的变形
6.1 双向有限自动机
6.2 多头有限状态自动机
6.3 概率有限自动机
6.4 加权有限自动机和数字图像
问题与解答
习题
第7章 下推自动机
7.1 下推自动机
7.2 空栈接受和终态接受的等价
7.3 CFG 和PDA 的等价
问题与解答
习题
第8章 上下文无关文法性质与分析
8.1 CFL 的泵引理
8.2 CFL 的封闭性
8.3 CFL 的判定性质
8.4 CFL 的子群
8.5 帕里克映射与帕里克定理
8.6 自嵌入性
8.7 同态下的特性
问题与解答
习题
第9章 图灵机
9.1 作为接受器的图灵机
9.2 作为计算设备的图灵机
9.3 图灵机的构造技术
问题与解答
习题
第10章 图灵机的变形
10.1 通用版本
10.2 受限图灵机
10.3 作为枚举器的图灵机
10.4 图灵机和0 型语言的等价
10.5 线性有界自动机
10.6 歌德尔编号
问题与解答
习题
第11章 通用图灵机及可判定性
11.1 图灵机的编码和枚举
11.2 递归和递归可枚举集
11.3 通用图灵机
11.4 问题, 实例和语言
11.5 莱斯定理
11.6 规约问题以证明不可判定性
11.7 波斯特对应问题
11.8 可计算函数
问题与解答
习题
第12章 时间与空间复杂度
12.1 RAM 模型
12.2 图灵机的时间与带复杂度
问题与解答
习题
第13章 最近的趋势及应用
13.1 正则重写
13.2 马库斯上下文文法
13.3 林登麦伊尔系统
13.4 文法系统及分布式自动机
第14章 一些新的计算模型
14.1 DNA 计算
14.2 膜计算
单项选择题(I)
单项选择题(II)
参考文献
版权页：插图：
《形式语言,自动机理论与计算导论》是国外计算机科学教材系列。
无
翻译很好，很满意。
才看了前面2章,就发现书中有太多(不下于十处)的排版错误, 该大小的写成小写, 符号写错,等等非常影响阅读.不建议购买