An Introduction to Formal Languages and Automata（形式语言与自动机导论）

引用

Linz, P., & Rodger, S. H. (2023). An Introduction to Formal Languages and Automata (7th ed.). Jones & Bartlett Learning.

章节概要

第七版分两部分共十七章。第一部分"Theory"即第六版的十四章，并补充了新习题；第二部分"Applications"是新增的，把前面的理论应用到编译器中的语法分析。其后是两个附录、部分习题的答案与提示，以及延伸阅读文献，全书约570页。标有星号的小节可以略去，不影响后续内容。每章末尾在原有习题之外，新增了一组较简单的"Introductory Exercises（入门习题）"。

第1章：Introduction to the Theory of Computation（计算理论导论）

复习数学预备知识（集合、函数与关系、图与树、证明技巧），然后引入本书的三个基本概念：语言、文法和自动机。一个选学小节概述了若干应用。

第2章：Finite Automata（有限自动机）

借助转移图定义确定型有限接受器，并用它定义正则语言；随后引入非确定型接受器，说明非确定性为何有用，并证明两者等价。一个选学小节讨论状态数的化简。

第3章：Regular Languages and Regular Grammars（正则语言与正则文法）

引入正则表达式，证明它恰好描述正则语言，并介绍它在描述简单模式中的用法。右线性文法和左线性文法被证明生成同一个语言族。

第4章：Properties of Regular Languages（正则语言的性质）

讨论在集合运算及其他运算下的封闭性、基本的判定问题，以及如何利用鸽巢原理和泵引理证明某个语言不是正则语言。

第5章：Context-Free Languages（上下文无关语言）

引入上下文无关文法、最左推导与最右推导以及推导树，继而讨论语法分析、成员判定和二义性，最后说明上下文无关文法在程序设计语言中的作用。

第6章：Simplification of Context-Free Grammars and Normal Forms（上下文无关文法的化简与范式）

说明如何消除无用产生式、λ产生式和单位产生式，并给出乔姆斯基范式和格雷巴赫范式。一个选学小节给出上下文无关文法的成员判定算法。

第7章：Pushdown Automata（下推自动机）

定义非确定型下推自动机，并从两个方向证明它与上下文无关文法等价；然后讨论确定型下推自动机和确定型上下文无关语言，另有一个选学小节讲它们的文法。

第8章：Properties of Context-Free Languages（上下文无关语言的性质）

给出上下文无关语言和线性语言的泵引理、封闭性质，以及上下文无关语言的若干可判定性质。

第9章：Turing Machines（图灵机）

把标准图灵机分别定义为语言接受器和转换器，说明如何组合多台图灵机完成复杂任务，并陈述图灵论题。

第10章：Other Models of Turing Machines（图灵机的其他模型）

考察各种变体（带停留选项的、半无限带的、离线图灵机）、具有更复杂存储的图灵机（多带和多维）、非确定型图灵机、通用图灵机和线性有界自动机，并确认哪些变体不会增加计算能力。

第11章：A Hierarchy of Formal Languages and Automata（形式语言与自动机的层次）

区分递归语言与递归可枚举语言，并给出不属于各自类别的语言；然后引入无限制文法和上下文有关文法，建立乔姆斯基层次。

第12章：Limits of Algorithmic Computation（算法计算的极限）

讨论可计算性与可判定性、停机问题、把一个不可判定问题归约到另一个问题、关于递归可枚举语言和上下文无关语言的不可判定问题，以及波斯特对应问题，最后简要谈到效率问题。

第13章：Other Models of Computation（其他计算模型）

介绍其他计算模型：原始递归函数和μ递归函数（含阿克曼函数）、波斯特系统，以及矩阵文法、马尔可夫算法和L系统等重写系统。

第14章：An Overview of Computational Complexity（计算复杂性概览）

把图灵机模型与复杂性联系起来，引入语言族和复杂性类，讨论P与NP、若干NP问题的例子、多项式时间归约和NP完全性，最后落在P是否等于NP这一悬而未决的问题上。

第15–17章：Compilers and Parsing（编译器与语法分析）；LL Parsing（LL语法分析）；LR Parsing（LR语法分析）

第二部分从编译器的工作、自顶向下与自底向上的语法分析以及FIRST和FOLLOW函数讲起。第16章为LL分析把上下文无关文法转换为非确定型下推自动机，构造LL(1)分析表和分析算法，并有一节讨论LL(k)。第17章对LR分析做同样的工作：项目与闭包、模拟分析栈的DFA、LR(1)分析表与算法、λ产生式以及分析冲突。

附录

附录A讨论有限状态转换器（米利机和摩尔机、两者的等价性、最小化及其局限）。附录B介绍JFLAP，一款用于构建和测试自动机与文法的免费交互式工具。

核心概念

第1–4章：基础与正则语言

• 语言、文法、自动机：本书的三个基本概念，在第1章中一并引入。
• 非确定性：允许存在多种可能的移动；对有限接受器而言，它带来便利，但不增加能力。
• 正则表达式：恰好描述有限自动机所接受语言的一种记法。
• 泵引理：所有正则语言都具有的性质，用来证明某个语言不是正则语言。

第5–8章：上下文无关语言

• 推导树与二义性：推导的结构，以及允许一个串有多棵推导树的文法。
• 乔姆斯基范式与格雷巴赫范式：任何上下文无关语言都可以采用的受限文法形式。
• 下推自动机：带栈的有限自动机，其非确定型与上下文无关文法等价。

第9–13章：图灵机与可计算性

• 图灵论题：任何机械计算都可以由图灵机完成这一主张。
• 通用图灵机：能根据任意其他图灵机的描述来模拟它的图灵机。
• 乔姆斯基层次：正则、上下文无关、上下文有关和递归可枚举这几个层层嵌套的语言族。
• 停机问题与归约：最基本的不可判定问题，以及证明其他问题不可判定的方法。

第14章：复杂性

• P与NP：可在确定型和非确定型多项式时间内求解的问题。
• NP完全性：在多项式时间归约意义下NP中最难的问题。

第15–17章：语法分析

• FIRST与FOLLOW：定义在文法符号上、用于构造分析表的函数。
• LL(1)与LR(1)分析：向前看一个符号、由分析表驱动的自顶向下和自底向上分析，从下推自动机推导而来。

评析

优点

• 直觉和例子先行。 序言称本书注重直观的动机和以例子说明概念，在简洁但难懂的论证与容易理解的论证之间选择后者，并用一个起动机作用的例子引出每个核心概念。
• 在解题中学习。 每节末尾的习题从顺着正文再走一两步的简单题到极难的题都有；第七版又在章末加入入门习题，作为通往较难习题的桥梁。书中给出部分习题的答案和提示。
• 直接回答"这有什么用"。 第二部分把下推自动机和文法应用于LL和LR语法分析；作者说，这是为了回应学生关于理论实际用途的疑问。
• 工具支持。 附录B介绍免费交互式工具JFLAP，序言强烈推荐用它来理解概念，并节省构造习题解答的时间。

局限

• 证明较为简略。 序言承认许多证明只给出思路，省略了常规细节；需要完整形式化证明的读者，得参考更严格的教材，或自己补全步骤。
• 复杂性只作概览。 计算复杂性只占一章，止于NP完全性；空间复杂性及更深入的主题都没有涉及。
• 一学期装不下。 序言指出，要在一学期内讲完第一部分的大部分内容就必须有所侧重；若还要讲第二部分，就得把第一部分后面的一些小节讲得轻一些。

在课程中的定位

在计算理论这门课的书单中，本书是一本平易的入门教材，按标准顺序从有限自动机讲到NP完全性。另一个入门选择是 MacCormick 的 What Can Be Computed?：它通过Python程序来讲可计算性和复杂性，有限自动机只占一章，没有专门讲文法或下推自动机的章节。如果课程在形式语言上花的时间较多，Linz 与 Rodger 更合适；两本书也可以很好地互补。

Kozen 的 Automata and Computability（由带完整证明的短讲组成）、Hopcroft、Motwani 与 Ullman 的 Introduction to Automata Theory, Languages, and Computation 以及 Sipser 的 Introduction to the Theory of Computation 覆盖相近的内容，证明更为形式化；觉得 Linz 的证明梗概过于简略的学生，可以去读这些书中对应的小节。Arora 与 Barak 的 Computational Complexity 是研究生教材，对复杂性的讨论远远超出第14章的概览。

如何使用本书

序言设定的读者是计算机科学和计算机工程专业的二、三年级本科生。先修要求包括：掌握一种高级程序设计语言，了解数据结构与算法的基础，以及一门必不可少的离散数学课程，内容涵盖集合、函数、关系、逻辑和数学推理。

• 核心（第一部分）： 按顺序读第1–12章；序言提醒，除标星号的小节（例如1.3、2.4、6.3、7.4）外，几乎没有什么可以跳过而不给后面带来麻烦。
• 可以从简： 序言指出，第一部分后半的许多小节可以从简处理或略去而不影响连贯性，由此可为第二部分腾出大约一周；讲其他计算模型的第13章就是合适的候选。
• 复杂性： 第14章初步介绍P、NP和NP完全性。
• 应用（第二部分）： 第15–17章适合准备修编译原理的学生，课时不够时也可以作为有指导的课外阅读。

先做入门习题，检验对每个定义的理解，再转向正式习题。把例子中的每个自动机和文法都在JFLAP中搭建出来，用字符串测试之后再动手写证明。书中只给出证明梗概的地方，自己把缺失的细节写出来；这正是序言所推荐的练习方式。