2.3 The Chomsky hierarchy of grammars and languages

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关(content-sensitive)	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关(content-free)	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则(Regular grammars)	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。

这里涉及到几个概念：上下文无关文法 ,BNF (Backus-Naur Form)（巴克斯-诺尔范式）经常用来表达上下文无关文法。 这里还要补充一个类型4 Finite-choice grammars.在该文法的右边不存在非终结符。