乔姆斯基谱系

乔姆斯基谱系将形式语言组织成四个嵌套的类别，每个类别都由语法规则的限制定义，并与一种独特的抽象机器相匹配。

Definition

乔姆斯基谱系是一种通过对其生成规则施加逐步增强的限制来对形式文法进行分类的方法，从而产生正则语言、上下文无关语言、上下文相关语言和递归可枚举语言类别，形成一个严格包含的链条。

Scope

本主题涵盖了四种语法类型——无限制语法、上下文相关语法、上下文无关语法和正则语法——它们的严格包含关系，以及与每个级别对应的自动机模型，即图灵机、线性有界自动机、下推自动机和有限自动机，以及区分这些级别的闭包和可判定性属性。

Core questions

• 语法规则的限制如何转化为内存和计算能力的限制？
• 为什么谱系的每个级别都严格包含在下一个级别中？
• 哪种自动机模型对应于每种语法类型？
• 随着谱系的提升，可判定性和闭包属性如何变化？

Key theories

语法-机器对应关系

每个语法类别都由特定的机器模型识别——正则语法由有限自动机识别，上下文无关语法由下推自动机识别，上下文相关语法由线性有界自动机识别，无限制语法由图灵机识别——这连接了计算的生成式描述和操作式描述。

语言类别的严格包含

每个级别都严格包含其下方的级别，这由具体的区分语言所证明，因此该谱系是一个表达能力递增的真正阶梯，而不是一组等效的描述。

Clinical relevance

该谱系是形式语言理论的组织图：它告诉编程语言、查询语言和协议规范的设计者，给定一类模式需要多少机器，并界定了什么是可判定的，什么是仅可识别的界限。

History

乔姆斯基在20世纪50年代末提出了该谱系，当时他正在寻求自然语言句法的形式模型。随着自动机理论在20世纪60年代的成熟，机器对应关系得以确立，其中Myhill引入了线性有界自动机，Kuroda阐明了上下文相关级别。

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

乔姆斯基谱系的四个级别是什么？

从弱到强依次是正则语言（类型3）、上下文无关语言（类型2）、上下文相关语言（类型1）和递归可枚举语言（类型0）。每个级别都放宽了对语法规则的限制，并对应于具有更多内存的机器。

自然语言是否被乔姆斯基谱系所涵盖？

该谱系最初的动机是语言学，但大多数语言学家认为自然语言并非上下文无关，而是处于一个通常被称为“轻度上下文相关”的级别。尽管人类语言与它的契合度不高，但该谱系在计算机科学中仍然是基础性的。