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

第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个学科形态。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性，从而培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。