本书介绍了形式语言和自动机的基本理论和基本方法,主要内容包括计算理论基础、文法和语言、上下文无关文法及其语言、有穷状态自动机、正则语言与正则文法、正则语言的性质、下推自动机与上下文无关文法、上下文无关语言的性质、图灵机、图灵机的其他模型和其他计算模型等内容。 本书可作为高等院校计算机科学与技术及相关专业的教材，也可作为教师、研究生或软件技术人员的参考书。

朱保平,1964年12月8日生，教授，南京理工大学博士研究生毕业，1987年至今就职于南京理工大学计算机科学与技术学院，现从事离散数学、数据结构、形式语言与自动机的教学工作。曾编箸教材如下：离散数学（第1版） 2006 300千字 北京理工大学出版社 离散数学（第2版） 2014 347千字 北京理工大学出版社离散数学概念 题解与自测 2009 210千字 北京理工大学出版社数理逻辑及其应用 1998 220千字 北京理工大学出版社�

“形式语言与自动机”是计算机科学与技术专业的重要理论基础课程，它不仅是计算机科学的核心课程，而且已成为电子信息类专业的热门课程。 形式语言与自动机是数学系统应用于计算的模型，形式语言是对语言的语法规则进行描述和分类的形式化方法；自动机是能够识别各种语言的自动化装置。形式语言与自动机在编译理论、人工智能、现代密码协议和通信等领域有着极其广泛的应用。 本书共分11章。第1章计算理论基础，介绍了离散数学的一些基础知识，主要包括集合及其表示，集合之间的关系，集合的运算，二元关系及其性质，等价关系与等价类，递归定义和递归证明，无向图、有向图、树；第2章文法和语言，包括文法的直观意义与形式定义，推导，归约，文法产生句型、句子和语言、文法的构造，乔姆斯基体系等内容；第3章上下文无关文法及其语言，主要介绍上下文无关文法的派生、派生树、文法的二义性、句法分析相关算法、上下文无关文法的化简、 chomsky和Greibach范式等内容；第4章有穷状态自动机，主要包括DFA和NFA的形式定义、DFA和NFA接受的语言、DFA和NFA的等价性、带空移动的NFA与NFA的等价性和DFA的最小化等内容；第5章正则语言与正则文法，包括正则表达式的定义、正则表达式与FA的等价性、正则文法与FA的等价性等内容；第6章正则语言的性质，包括正则语言的泵引理的证明及其应用，正则语言的封闭性，Myhill Nerode定理与正则语言判定算法。第7章下推自动机与上下文无关文法，包括下推自动机的定义及其接受的语言、下推自动机的构造方法及与上下文无关文法的等价性、双栈自动机等；第8章上下文无关语言的性质，包括上下文无关语...