为什么一个语言学家搭建了计算机科学的基石（历史）
自动机层级理论出自语言学家诺姆·乔姆斯基（Noam Chomsky）之手，这件事本身就很出人意料（1956 年论文 Three Models for the Description of Language；1957 年《句法结构》Syntactic Structures）。搭起这座桥的，是一个被转化成数学命题的具体论证。
靶子：语言不是有限状态的
20 世纪 50 年代的语言学以行为主义（斯金纳）和结构主义为主流，而香农的信息论又让有限状态 / 马尔可夫式的语言模型一度大为流行——把一个句子看成词的随机链。乔姆斯基的决定性一击是一个数学式的反驳：
自然语言存在无界的嵌套（中心嵌入）依存关系——例如"猫追的狗咬过的老鼠死了"这类句子，开启的成分必须与任意远处的收尾成分相匹配。有限自动机没有记忆去统计嵌套的深度，因此没有任何有限状态（马尔可夫）模型能恰好生成全部合法句子而不多不少。
这正是[[regular-languages|aⁿbⁿ 论证]]的翻版：语言至少需要一个栈（上下文无关）。一个关于人类心智的论断，就此变成了一条关于自动机的定理。
生成语法 → 层级理论
乔姆斯基把语法重新表述为一个形式化的生成系统——一组产生出全部且仅有合法字符串的重写规则（借鉴了埃米尔·波斯特（Emil Post）的产生式/重写系统以及 Thue 的工作）。层级理论（Type 0–3）回答的是一个纯数学问题，而这个问题是语言学逼出来的："重写规则上的每一层限制，各自换来多少生成能力？"——而这个答案恰好与各类自动机（也就是各种记忆能力）一一对应。
为什么它对计算机科学如此重要
这套形式化理论又反过来冲击了计算机科学：
- 上下文无关文法变成了编程语言的语法——巴科斯范式（Backus–Naur Form，ALGOL 60 采用）本质上就是一个 CFG；解析与编译器的整套理论都建立在 Type 2–3 之上。
- 乔姆斯基–舒岑贝格尔（与一位数学家合作）为上下文无关语言建立了一套代数理论。
于是一个认知科学问题（"人类的句法究竟是什么？"）催生了编译器理论——真正不平凡的地方恰恰在于：一个人文学科侧的问题，经由"把语法形式化为重写系统、再追问其生成能力"这一招，产出了一个奠基性的计算框架。
留存至今的经验性论断
这套层级理论不只是一套分类法：把人类语言定位在弱上下文相关（高于上下文无关、低于完整的上下文相关）这件事本身，就是一个关于心智的、有实质内容且数学上精确的论断——是经验科学与形式计算之间那种难得一见的桥梁。