乔姆斯基谱系 乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系是由语言学家诺姆乔姆斯基于年提出的它包括四个层次 型文法无限制文法或短语结构文法包括所有的文法该类型的文法能够产生所有可被图灵机识别的语言可被图灵机识别的语言是指能够使图灵机停机的字串这类语言又被称为递归可枚举语言注意递归可枚举语言与递归语言的区别后者是前者的一个真子集是能够被一个总停机的图灵机判定的语言 型文法上下文相关文法生成上下文相关语言这种文法的产生式规则取如 αAβ  αγβ 一样的形式这里的A 是非终结符号而 α β 和 γ 是包含非终结符号与终结符号的字串α β 可以是空串但 γ 必须不能是空串这种文法也可以包含规则 Sε 但此时文法的任何产生式规则都不能在右侧包含 S 这种文法规定的语言可以被线性有界非确定图灵机接受 型文法上下文无关文法生成上下文无关语言这种文法的产生式规则取如 A  γ 一样的形式这里的A 是非终结符号γ 是包含非终结符号与终结符号的字串这种文法规定的语言可以被非确定下推自动机接受上下文无关语言为大多数程序设计语言的语法提供了理论基础 型文法正规文法生成正规语言这种文法要求产生式的左侧只能包含一个非终结符号产生式的右侧只能是空串一个终结符号或者一个终结符号后随一个非终结符号如果所有产生式的右侧都不含初始符号 S 规则 S  ε 也允许出现这种文法规定的语言可以被有限状态自动机接受也可以通过正则表达式来获得正规语言通常用来定义检索模式或者程序设计语言中的词法结构 正规语言类包含于上下文无关语言类上下文无关语言类包含于上下文相关语言类上下文相关语言类包含于递归可枚举语言类这里的包含都是集合的真包含关系也就是说存在递归可枚举语言不属于上下文相关语言类存在上下文相关语言不属于上下文无关语言类存在上下文无关语言不属于正规语言类 下表总结了上述四种类型的文法的主要特点