"本书介绍形式语言与自动机理论相关的基础知识，并以自动机和文法为轴线，突出在计算机科学与技术领域有重要应用背景的内容。本书的知识体系可从密切相关的5个层面体现：有限自动机、正规表达式与正规语言；上下文无关文法、下推自动机与上下文无关语言；经典分析文法及相关自动机；图灵机与递归可枚举语言；计算理论初步知识。 学习本书内容，有助于培养计算机科学与技术基础理论方面的素养，提高逻辑思维和解决相关实际问题的能力，并为计算机领域专业知识的深入学习和理解，以及从事科学研究或技术开发工作奠定坚实的基础。 本书可作为高等院校计算机科学与技术相关专业本科/研究生教材或课外学习资料，也可作为相关教师、科研或工程技术人员的参考书。 "

前言 虽然人们很早就开始了关于计算以及计算模型相关问题的探讨，然而可以认为正是计算机的出现和计算技术的发展，形式语言与自动机理论才被深入和广泛地研究并推广应用，成为计算机科学与技术基础理论的重要组成部分。20世纪60—70年代，相关研究达到高峰。一方面，真实计算机的出现促进了人们对计算机能做什么以及能做到什么的认知需求，这个时期可计算性理论受到广泛重视，特别是计算复杂性理论的研究也得到了飞速发展。另一方面，同一时期形式语言与自动机理论在计算机高级语言编译技术中的应用逐步成熟，深刻影响了计算机技术的发展。这两方面足以奠定形式语言与自动机理论在计算机科学与技术领域的突出地位。 形式语言与自动机理论所讨论的内容以“计算模型”为主线。不同的计算模型有不同的计算能力，即不同的问题求解能力。“形式语言”是抽象的数学对象，用符号串的集合对问题进行抽象描述，表示要解决的问题“是什么”。在这一背景下，“语言”和“问题”本质上是等同的。而“自动机”则泛指采用各种方式刻画的计算模型，对应“如何做”去解决某一问题，通常体现为如何定义或者如何接受该问题所对应的语言。 通常的“自动机”计算模型，往往具有显式的“可执行”或“可模拟”特征，可以通过状态、动作及状态变化刻画其语义，即如何接受或处理语言中的字符串。本书涉及几种重要的自动机计算模型： 有限（有穷）自动机、下推自动机、归约自动机，以及图灵机。 此外，一些语言计算模型，如本书主要讨论的正规表达式和上下文无关文法，它们看起来像是针对语言的精确（或形式化）定义，并无明显的“可执行”或“可模拟”特征，但它们各自均对应等价的自动机模型。本书也将...