1.2.1 乔姆斯基谱系（Chomsky Hierarchy）

文档摘要

1.2.1 乔姆斯基谱系（Chomsky Hierarchy） 1.2.1 乔姆斯基谱系（Chomsky Hierarchy）想象一下，你正在设计一个编程语言的解析器：用户输入一段代码，你需要精确判断它是否合法，并构建出语法树。这不是科幻，而是形式语言理论的核心战场。乔姆斯基谱系，正是这份战场的地图，由诺姆·乔姆斯基在1956年提出，它将文法（grammar）按生成能力从弱到强分层为四型：Type-3（正则文法）、Type-2（上下文无关文法）、Type-1（上下文相关文法）和Type-0（无限制文法）。每一层对应特定的自动机模型，决定了语言的“可计算性”和解析复杂度。为什么这套谱系如此关键？因为它不只是理论抽象，而是编译器、NLP解析器乃至AI代码生成的基石。