乔姆斯基谱系
维基百科，自由的百科全书
乔姆斯基体系是刻画形式文法表达能力的一个分类谱系，是由诺姆·乔姆斯基于1956年提出的。它包括四个层次：
- 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
- 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
- 2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
- 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。
下表总结了上述四种类型的文法的主要特点：
| 文法 | 语言 | 自动机 | 产生式规则 |
|---|---|---|---|
| 0-型 | 递归可枚举语言 | 图灵机 | 无限制 |
| 1-型 | 上下文相关语言 | 线性有界非确定图灵机 | αAβ -> αγβ |
| 2-型 | 上下文无关语言 | 非确定下推自动机 | A -> γ |
| 3-型 | 正规语言 | 有限状态自动机 | A -> aB A -> a |
[编辑] 参考文献
- Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
- Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112
| 自动机理论: 形式语言和形式文法 | |||
|---|---|---|---|
| 乔姆斯基层级 | 文法 | 语言 | 极小自动机 |
| 类型 0 | 无限制 | 递归可枚举 | 图灵机 |
| n/a | (无公用名) | 递归 | 判定器 |
| 类型 1 | 上下文有关 | 上下文有关 | 线性有界 |
| n/a | 附标 | 附标 | 嵌套堆栈 |
| n/a | 树-邻接 | 适度上下文有关 | 嵌入下推 |
| 类型 2 | 上下文无关 | 上下文无关 | 非确定下推 |
| n/a | 确定上下文无关 | 确定上下文无关 | 确定下推 |
| 类型 3 | 正则 | 正则 | 有限 |
| 每个语言或文法范畴都是其直接上面的范畴的真子集。 | |||
