前言

虽然人们很早就开始了关于计算以及计算模型相关问题的探讨，然而可以认为正是计算机的出现和计算技术的发展，形式语言与自动机理论才被深入和广泛地研究并推广应用，成为计算机科学与技术基础理论的重要组成部分。20世纪60—70年代，相关研究达到高峰。一方面，真实计算机的出现促进了人们对计算机能做什么以及能做到什么的认知需求，这个时期可计算性理论受到广泛重视，特别是计算复杂性理论的研究也得到了飞速发展。另一方面，同一时期形式语言与自动机理论在计算机高级语言编译技术中的应用逐步成熟，深刻影响了计算机技术的发展。这两方面足以奠定形式语言与自动机理论在计算机科学与技术领域的突出地位。

形式语言与自动机理论所讨论的内容以“计算模型”为主线。不同的计算模型有不同的计算能力，即不同的问题求解能力。“形式语言”是抽象的数学对象，用符号串的集合对问题进行抽象描述，表示要解决的问题“是什么”。在这一背景下，“语言”和“问题”本质上是等同的。而“自动机”则泛指采用各种方式刻画的计算模型，对应“如何做”去解决某一问题，通常体现为如何定义或者如何接受该问题所对应的语言。

通常的“自动机”计算模型，往往具有显式的“可执行”或“可模拟”特征，可以通过状态、动作及状态变化刻画其语义，即如何接受或处理语言中的字符串。本书涉及几种重要的自动机计算模型： 有限（有穷）自动机、下推自动机、归约自动机，以及图灵机。

此外，一些语言计算模型，如本书主要讨论的正规表达式和上下文无关文法，它们看起来像是针对语言的精确（或形式化）定义，并无明显的“可执行”或“可模拟”特征，但它们各自均对应等价的自动机模型。本书也将正规表达式、上下文无关文法等称为计算模型。

在形式语言与自动机理论体系中，通常是针对典型的语言类（或问题类）进行相对独立的专门讨论，研究这些语言类各自的共性问题，以及通用的问题求解方法。本书很大篇幅是面向在实际应用中发挥着重要作用的语言类，包括正规语言、上下文无关语言以及确定的上下文无关语言，探讨这些语言本身的特性、相关计算模型，以及这些计算模型之间的相互关系。

对于正规语言类，第3～5章主要介绍正规语言的几种计算模型，包括正规表达式和3种有限自动机，以及它们之间的相互等价性。第6章介绍正规语言本身的特性，如重要性质、运算以及基本的判定问题。

针对上下文无关语言类，第2、7、8章介绍上下文无关语言的两种计算模型——上下文无关文法和下推自动机，以及二者之间的相互等价性。第10章介绍上下文无关文法的变换以及重要的范式。第11章介绍上下文无关语言本身的特性，同样包括其重要性质、运算以及基本的判定问题。

第9章通过介绍确定下推自动机，引入确定的上下文无关语言类。确定下推自动机和确定的上下文无关语言，与实际应用中的语法分析程序构造原理密切相关。

第12章主要介绍在实践中应用广泛的两类分析文法——LL(k)和LR(k)文法以及相应的自动机模型，包括相关的基础理论及其在语法分析程序构造中的应用。下推自动机可以很好地刻画自顶向下语法分析过程，相应地，自顶向下的LL(k)分析程序容易对应到与之等价的确定下推自动机。对于常规的自底向上语法分析过程以及LR(k)分析程序，虽然可以定义扩展的下推自动机或确定下推自动机与之对应，然而二者之间的等价变换并不自然、直接和容易理解。为此，本书引入归约自动机，以及相应的确定归约自动机，旨在更加合理地解决这一问题。

第13章介绍图灵机计算模型，涉及可计算性理论中两类重要的语言——递归可枚举语言与递归语言。

第14章介绍有关计算理论（可计算性与计算复杂性理论）的初步知识。

本书内容的学习不需要特定的基础，仅需具备基本的数学素养和简单的形式逻辑/证明基础，如第1章所涉及的集合、演绎及证明等方面的基本概念、方法和技能。对于有条件的读者（如计算机专业的学生），能预先掌握部分“离散数学”的知识更好，包括数理逻辑、集合与代数结构、图论等方面的基础知识，有利于更高效地学习和理解。

本书可用作“形式语言与自动机”以及“编译原理”相关课程的教材或教学参考书。作者在清华大学计算机系开设的“形式语言与自动机”本科生课程（32学时），以及在北京语言大学为研究生讲授的同名课程（48学时），教学内容共13讲，与本书中除第12章外的其余13章相吻合。课程中未涵盖的内容以及第12章整体均以“*”标记。

对于“编译原理”课程的教师或学生，在讲授或学习词法分析和语法分析的设计原理和方法时，本书中有关正规表达式、有限自动机、上下文无关文法、下推自动机、分析文法及归约自动机的相应章节，可作为教学过程以及课后提升的重要参考素材。

从教学改革角度，还可以尝试以本书整体内容为基础开设独立的课程。这会影响到编译相关课程的教学理念，作者认为至少有两方面好处： 一方面，相比常规编译课程中偏原理的内容，本书相关章节更加系统化，更容易理解与融会贯通，能给学生的学习带来更加全面和严谨的体验；另一方面，可以简化甚至取消编译教学中偏重原理的内容，大大减轻教学负担，同时可以利用节省出来的课时适当加强实用的编译器设计技术以及实践教学方面的内容。这在一定程度上或许会增加教学难度，但从作者多年从事“形式语言与自动机”和“编译原理”两门课程教学的经验看，国内大学相当一部分学生并不畏惧系统性地学习基础理论知识（可类比“离散数学”之类的课程）。

归约自动机是本书新引入的概念（不排除学术界曾有过相似的计算模型），在讨论自底向上语法分析时更加简洁、方便。与归约自动机相关的内容仅出现在第12章，且均以“+”标记，可选择性学习或参考。

本书写作过程中，先后与张素琴、董渊、陈渝、刘洋、姚海龙、季铮锋、王龙、杨天麟、钱学海、段斯斯等老师以及许多助教同学共同承担上述两门课程的教学工作，作者享受其中、受益匪浅。

受作者知识水平所限，书中难免存在不当和疏漏之处，诚请读者批评指正。

作者2026年1月