
乔姆斯基分层是计算机科学中对形式语言的分类体系,由诺姆·乔姆斯基于20世纪50年代提出,通过四类文法界定语言生成能力:0型(递归可枚举语言)、1型(上下文相关语言)、2型(上下文无关语言)和3型(正则语言),分别对应图灵机、线性有界自动机、下推自动机和有限自动机识别。
该分层规定高级语言默认属于低级类别,但反向不成立。扩展层次表明线性语言构成上下文无关语言的子集,确定性上下文无关语言与正则语言存在非包含关系。 正则文法存在左线性文法和右线性文法两种等价形式。
该理论受到数学家波斯特产生式系统启发,分层体系为计算语言学问题研究提供了难度排序框架。
想要了解更多“乔姆斯基分层”的信息,请点击:乔姆斯基分层百科
