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

　　第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)

　　形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其多年来在大学讲授该门课程的经验和体会，选择和组织有关内容撰写而成。不仅含有有关正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识，更涉及到本学科方法论中所包含的3个学科形态。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性，从而培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。