乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系,是由诺姆·乔姆斯基于1956年提出的。它包括四个层次:
- 0-型文法(无限制文法或短语结构文法)包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串,这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别,后者是前者的一个真子集,是能够被一个总停机的图灵机判定的语言。
- 1-型文法(上下文相关文法)生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号,而 α, β 和 γ 是包含非终结符号与终结符号的字串;α, β 可以是空串,但 γ 必须不能是空串;这种文法也可以包含规则 S->ε ,但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
- 2-型文法(上下文无关文法)生成上下文无关语...