“形式语言与自动机”是计算机科学与技术专业的重要理论基础课程，它不仅是计算机科学的核心课程，而且已成为电子信息类专业的热门课程。

形式语言与自动机是数学系统应用于计算的模型，形式语言是对语言的语法规则进行描述和分类的形式化方法；自动机是能够识别各种语言的自动化装置。形式语言与自动机在编译理论、人工智能、现代密码协议和通信等领域有着极其广泛的应用。

本书共分11章。第1章计算理论基础，介绍了离散数学的一些基础知识，主要包括集合及其表示，集合之间的关系，集合的运算，二元关系及其性质，等价关系与等价类，递归定义和递归证明，无向图、有向图、树；第2章文法和语言，包括文法的直观意义与形式定义，推导，归约，文法产生句型、句子和语言、文法的构造，乔姆斯基体系等内容；第3章上下文无关文法及其语言，主要介绍上下文无关文法的派生、派生树、文法的二义性、句法分析相关算法、上下文无关文法的化简、 chomsky和Greibach范式等内容；第4章有穷状态自动机，主要包括DFA和NFA的形式定义、DFA和NFA接受的语言、DFA和NFA的等价性、带空移动的NFA与NFA的等价性和DFA的最小化等内容；第5章正则语言与正则文法，包括正则表达式的定义、正则表达式与FA的等价性、正则文法与FA的等价性等内容；第6章正则语言的性质，包括正则语言的泵引理的证明及其应用，正则语言的封闭性，Myhill Nerode定理与正则语言判定算法。第7章下推自动机与上下文无关文法，包括下推自动机的定义及其接受的语言、下推自动机的构造方法及与上下文无关文法的等价性、双栈自动机等；第8章上下文无关语言的性质，包括上下文无关语言的泵引理的应用、上下文无关语言的封闭性及判定算法。第9章图灵机，包括图灵机作为一个计算模型的基本定义、图灵机接受的语言、图灵机转换器和一些完成复杂任务的图灵机等；第10章图灵机的其他模型，包括带不动选择图灵机、多道图灵机、单向无穷带图灵机、离线图灵机、多带（头）图灵机和线性有界自动机等内容；第11章其他计算模型，主要包括递归函数的定义、递归函数的扩展理解、波斯特系统、矩阵文法和马尔可夫算法等内容。

本书第1～第5章、第10、第11章由朱保平编著，第6、第7章由徐建编著，第8、第9章由李千目编著。

由于作者水平有限，书中难免存在疏漏和不足之处，恳请读者和同行批评指正。

编著者