形式文法与乔姆斯基谱系

1956 年，一位年轻的语言学家在 IRE《信息论汇刊》上发表了一篇论文：《语言描述的三个模型》（"Three Models for the Description of Language"）。他的问题是语言学的：如何用数学方法描述人类语言的结构？然而，他的答案成为了计算机科学的核心理论之一。

这位语言学家是诺姆·乔姆斯基（Noam Chomsky）。他将形式文法（formal grammars）分成了四个层级——后来被称为乔姆斯基谱系（Chomsky Hierarchy）——而这四个层级恰好对应了四种计算机器的计算能力。这个对应，是 20 世纪理论计算机科学最美丽的结构之一。

破除误解：形式文法不只是"语法规则"#

在日常语言中，"语法"是关于正确用词和标点的规则。在计算机科学里，"形式文法"（formal grammar）是一个精确的数学对象，用来生成（generate）或识别（recognize）一类字符串。

一个形式文法定义了一种形式语言（formal language）——即所有"合法"字符串的集合。例如，所有配对的括号序列 ()、(())、(()())、((())) 等构成一种形式语言；所有 C 语言程序构成另一种形式语言。

形式文法理论的核心问题是：什么样的语言，需要什么样的生成规则，以及对应地，什么样的机器才能识别它？

现场：语言学遇上计算理论#

乔姆斯基当时面对的是语言学问题：当时的结构主义语言学用有限状态机（finite-state machine）描述语言结构。他证明这不够用——英语中的某些结构（如"句子中嵌套句子"的依存关系）需要比有限状态机更强的机制。

值得区分的是乔姆斯基自己的几篇文本，它们各自承担的论证并不相同。1956 年那篇论文比较了三种模型——有限状态的马尔可夫过程、短语结构文法、转换文法——论证前两者不足以描述自然语言；1957 年的《句法结构》（Syntactic Structures，Mouton 出版）把这套论证带给了语言学界。而真正给出严格数学定义的是 1959 年发表于《信息与控制》（Information and Control）的《论文法的某些形式性质》（On Certain Formal Properties of Grammars）：四类文法的层级在那里被形式化，并与产生式规则的形状精确挂钩。今天所说的"乔姆斯基谱系"，在技术上指的正是 1959 年这篇论文里的分类。

与此同时，艾伦·图灵（Alan Turing）在 1930 年代定义了图灵机，斯蒂芬·克莱尼（Stephen Kleene）在 1950 年代研究了有限自动机（finite automata）和正则语言（regular languages）。形式语言理论和自动机理论在 1950–1960 年代深度融合，乔姆斯基谱系是这个融合的核心成果。

乔姆斯基谱系：四个层级#

乔姆斯基谱系把形式文法分成四类（类型 0 到类型 3），形成一个严格的包含关系：

$$\text{正则语言} \subset \text{上下文无关语言} \subset \text{上下文有关语言} \subset \text{递归可枚举语言}$$

每一层都比上一层更强大（能描述更复杂的语言），对应地需要更强大的机器才能识别。

类型 3：正则文法与正则语言#

生成规则形式：$A \to aB$ 或 $A \to a$（只允许"一个非终结符产生一个终结符和至多一个非终结符"）

对应机器：有限状态自动机（Finite Automaton，FA）

能描述的语言举例：所有以 ab 结尾的字符串；所有只含 0 和 1 且 0 的个数为偶数的字符串；电话号码的格式（如 \d{3}-\d{4}）。

实际应用：正则表达式（Regular Expressions，regex）描述的正是正则语言。grep、代码编辑器中的搜索、邮箱格式校验，都使用有限状态自动机在幕后识别正则语言。

局限：正则语言不能描述任意深度的嵌套结构。例如，"所有配对括号序列"不是正则语言——有限状态机没有内存，它无法记住自己见过多少个左括号。

代数刻画：正则语言还有一层与具体机器无关的刻画——Myhill–Nerode 定理（1957–1958）。按"两个前缀接上任何后缀后是否同进同出该语言"定义等价关系，语言是正则的当且仅当这个等价关系只有有限个等价类；而且等价类的数目恰好等于识别该语言的最小自动机的状态数。这把"需要多少记忆"变成了语言的内在属性，也保证了最小自动机的存在与唯一。

类型 2：上下文无关文法与上下文无关语言#

生成规则形式：$A \to \gamma$（左边只能是单个非终结符，右边可以是任意符号序列）

对应机器：下推自动机（Pushdown Automaton，PDA）——有一个无限大的栈（stack）的有限状态机

能描述的语言举例：所有配对括号序列；算术表达式（如 $3 + (4 \times (5 - 2))$）；大多数编程语言的语法。

实际应用：编程语言的语法几乎都是上下文无关的。 每一种编程语言（C、Python、Java、JavaScript）都有一份 BNF 或 EBNF 形式的语法定义，这就是一个上下文无关文法。编译器的语法分析器（parser）就是一个下推自动机的实现。

这个实践的起点恰好在谱系诞生前后。1959 年，约翰·巴科斯（John Backus）在巴黎的 UNESCO 信息处理国际会议上提出了描述语言语法的形式记号；1960 年，彼得·瑙尔（Peter Naur）主编的《ALGOL 60 报告》用它完整规定了一门编程语言的语法，BNF（巴科斯-瑙尔范式）由此得名。从那以后，"一门语言的语法是什么"变成一个可以精确对错的数学问题，而不再是手册作者的文风问题。

局限：上下文无关文法不能描述"类型一致性"（如变量使用前必须声明）。这类约束需要更强的机制（在实际编译器中用符号表和语义分析实现，而不是文法本身）。

两件技术性工具值得点名。其一是乔姆斯基范式：任何上下文无关文法都可以等价改写为规则形如 $A \to BC$ 或 $A \to a$ 的范式，CYK 算法的动态规划正是在这种二分支结构上自底向上展开的（Kasami 1965、Younger 1967 与 Cocke 等人先后独立提出）。其二是确定性子类：Knuth 1965 年证明，LR(k) 文法恰好生成被确定性下推自动机识别的语言——自左向右扫描、向前看至多 $k$ 个符号即可决定每一步归约，因而线性时间可解析。类型 2 的内部由此又分出一道同样严格的层级：确定性上下文无关语言只是上下文无关语言的真子集。

类型 1：上下文有关文法与上下文有关语言#

生成规则形式：$\alpha A \beta \to \alpha \gamma \beta$（非终结符 $A$ 可以产生 $\gamma$，但只有在上下文 $\alpha \cdot \beta$ 中才允许）

对应机器：线性有界自动机（Linear Bounded Automaton，LBA）——内存大小与输入长度成正比的图灵机

能描述的语言举例：$\{a^n b^n c^n \mid n \geq 1\}$（等数量的 a、b、c）；自然语言中某些依存关系（虽然存在争议，自然语言是否是上下文有关的，是语言学的一个未解问题）。

局限：上下文有关语言的识别问题是 PSPACE-Complete 的（即使比多项式时间更难），在实践中很少直接使用。

这一层还悬着自动机理论中最古老的开放问题之一。1964 年，黑田成幸（S.-Y. Kuroda）证明了上下文有关语言与线性有界自动机的对应，并留下两个著名问题：非确定 LBA 与确定 LBA 是否等价？上下文有关语言在补运算下是否封闭？他还证明了若第二问的答案为否，则第一问亦然。1987 年，Immerman 与 Szelepcsényi 各自独立证明了第二问的答案是肯定的——非确定空间在补运算下封闭，证明之简洁出乎学界意料。但第一问，即所谓的 LBA 问题，六十多年后的今天仍然没有答案。

类型 0：无约束文法与递归可枚举语言#

生成规则形式：$\alpha \to \beta$（无任何约束）

对应机器：图灵机（Turing Machine）

能描述的语言：所有图灵机可以识别的语言——即"停机后输出接受"的语言。

这正是可计算性理论的边界：图灵机能识别的语言，正好是递归可枚举语言。 不在这个类里的语言，没有任何机器能识别。

"不可识别"并不是抽象的恐吓。波斯特对应问题（Emil Post 1946 年提出）就是一个具体的例子：给定有限多对字符串"骨牌"，问能否排出一个序列，使上下两行拼出同一个字符串。规则一句话就能讲清，却不存在任何算法能对一切实例给出答案。它还是许多文法层面不可判定结果的源头——"两个上下文无关文法是否等价""一个文法是否有歧义"，都可以通过归约自波斯特对应问题来证明。

谱系的对称性：机器与语言的对应#

这张对应表不是偶然的——它反映了计算能力和语言表达力之间的深刻等价关系。

泵引理：证明语言不属于某一层级#

如何证明某个语言不是正则语言，或不是上下文无关语言？这需要用到泵引理（Pumping Lemma）：

正则语言泵引理：若 $L$ 是正则语言，则存在泵长度 $p$，使得对任意 $s \in L$，$|s| \geq p$ 时，$s$ 可以写成 $s = xyz$，满足：$|xy| \leq p$，$|y| \geq 1$，且对所有 $i \geq 0$，$xy^iz \in L$（"y 段"可以任意重复多次，结果仍在语言内）。

用泵引理证明 $\{a^n b^n\}$ 不是正则语言：假设它是正则语言，取 $s = a^p b^p$，按引理分解为 $xyz$，其中 $|xy| \leq p$ 意味着 $y$ 只含 $a$。重复 $y$ 两次得到 $xy^2z = a^{p+|y|}b^p$，这里 $a$ 的数量多于 $b$，不在语言内——矛盾。

泵引理在每一层都有对应版本。上下文无关语言的版本（Bar-Hillel、Perles、Shamir，1961，常称 uvwxy 定理）说：足够长的句子可以分解为 $uvwxy$，其中 $v$ 与 $x$ 两段可以同时"泵"任意多次而不离开语言。用它证明 $\{a^n b^n c^n\}$ 不是上下文无关的，只需指出泵出的两段无法同时维持三路计数——一个栈做不到的事，任何上下文无关文法都做不到。

这类证明是理论计算机科学课程中的基本技能训练，也是理解语言层级边界的关键工具。

层级之外：哪些问题是可判定的#

谱系区分的不只是"能说什么"，还有"能问什么"。成员资格——某个字符串是否属于给定语言——在类型 1 及以下都可判定：上下文有关文法的推导不会使中间串变短，搜索空间因此有限；到了类型 0，成员资格问题就成了停机问题本身。

再问得细一点：空性与有穷性（文法是否生成空语言、是否生成无穷多个句子）在类型 2 仍然可判定；而"两个文法是否生成同一语言"这个看似朴素的问题，在类型 3 有完整的算法，到类型 2 就已经不可判定。这正是工程上把编程语言文法限制在确定性子类的深层动机：只有在 LR(k) 这类受限文法之内，等价与歧义等问题才有希望得到机械的回答。

实际影响：编译器与解析器#

乔姆斯基谱系在实践中最重要的应用是编译器的前端设计：

• 词法分析（Lexical Analysis，Lexer）：把源代码字符流切割成词元（token，如关键字、标识符、数字）。这是正则语言的任务，用有限状态自动机（在实践中用 flex、re2c 等工具自动生成）。
• 语法分析（Syntax Analysis，Parser）：按文法规则把词元序列组装成语法树（AST，Abstract Syntax Tree）。这是上下文无关语言的任务，用下推自动机实现（在实践中有 LL 分析器、LR 分析器，以及 yacc、Bison、ANTLR 等工具）。

这个两阶段分工——词法+语法——几乎是所有编程语言编译器的标准架构，理论基础正是正则文法和上下文无关文法的层级差异。

自然语言是哪一类？#

乔姆斯基谱系最初的动机是语言学，但自然语言（英语、中文等）究竟属于哪一层级，至今有争议。

早期（1957 年），乔姆斯基认为正则语言不够，需要上下文无关文法。但后来的研究发现，瑞士德语中存在某些交叉依赖的句子结构（如 Jan sah Leo tanze，"Jan 看见 Leo 跳舞"中的主谓宾嵌套），这被认为超出了上下文无关文法的能力，暗示自然语言至少需要弱上下文有关（mildly context-sensitive）的文法。

这场争论的性质比表面上微妙。自然语言没有形式语言意义上的"全集"——任何有限的语料都可以被某台有限状态机逐条背下来——所以争论的对象其实是最能解释语言结构规律性的文法类，而不是某个集合的归属。1985 年，Joshi 提出树邻接文法（TAG）与"轻度上下文有关"的范畴：比上下文无关文法恰强一点，能生成交叉依存，又保持多项式时间可解析。不少计算语言学家认为这是自然语言语法复杂度目前最合理的候选位置——但"合理位置"与"定论"之间，至今仍隔着经验与形式两方面的分歧。

跨域连接#

• 句法：生成文法的核心主张是有限规则生成无限句子，而嵌套结构要求机器带一份可增长的记忆。这把"语言有多复杂"变成可判定的层级问题：证明某语言不在某一层，用的是泵引理这类纯组合论证，与语感、与母语者的判断都无关，只与串的形状有关。
• 斯金纳与乔姆斯基之争：谱系是那场论战中最硬的一件武器。若语言只是刺激—反应的联想链条，它至多是有限状态的；而嵌套依存超出有限状态的能力，因此联想链条不足以说明语言能力。这一步是形式论证，不是关于学习动机或强化历史的争辩，也因此不能靠更多行为数据反驳。
• 一语习得：自然语言究竟落在哪一层至今没有定论，较普遍的判断是它超出上下文无关、但只轻微超出。这个位置直接影响可学性论证：目标语言类越大，从有限样例中把它确定下来所需的先天约束就越强，反之越弱。层级之争因而不是分类癖好，它牵着习得理论的赌注。
• 自然语言处理：如今的语言模型不使用任何谱系，直接对分布建模，因而绕开了"属于哪一层"的问题。但绕开不等于取消：谱系仍是衡量一种机制表达力上限的坐标，也是判断某类结构是否原则上超出某类模型的工具。
• 编程语言设计：编程语言的语法被自愿限制在上下文无关甚至更窄的子类里。这不是审美，而是为了让解析线性可做且无歧义；类型一致、先声明后使用这类约束因此被推到语义阶段，用符号表而不是文法来管——分层不是实现细节，是层级定理的直接安排。

参考文献#

• Chomsky, N. Three Models for the Description of Language. IRE Transactions on Information Theory 2(3) (1956): 113–124. （原始论文）
• Chomsky, N. Syntactic Structures. Mouton (1957). （面向语言学界的论证）
• Chomsky, N. On Certain Formal Properties of Grammars. Information and Control 2(2) (1959): 137–167. （谱系的正式定义）
• Naur, P. (ed.) Report on the Algorithmic Language ALGOL 60. Communications of the ACM 3(5) (1960): 299–314. （BNF 的首次完整应用）
• Bar-Hillel, Y., Perles, M. & Shamir, E. On Formal Properties of Simple Phrase Structure Grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14 (1961): 143–172. （上下文无关语言泵引理）
• Kuroda, S.-Y. Classes of Languages and Linear-Bounded Automata. Information and Control 7(2) (1964): 207–223.
• Immerman, N. Nondeterministic Space Is Closed Under Complementation. SIAM Journal on Computing 17(5) (1988): 935–938.
• Post, E. L. A Variant of a Recursively Unsolvable Problem. Bulletin of the American Mathematical Society 52 (1946): 264–268.
• Shieber, S. M. Evidence Against the Context-Freeness of Natural Language. Linguistics and Philosophy 8 (1985): 333–343.
• Sipser, M. Introduction to the Theory of Computation. 3rd ed. Cengage (2012). 第 2–3 章. （乔姆斯基谱系的标准教材处理）
• Hopcroft, J. E., Motwani, R. & Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Addison-Wesley (2006). （HMU，自动机理论的权威教材）