最近一两周编译原理课上面都是讲乔姆斯基谱系，也就是通常所说的0型文法，1型文法，2型文法以及3型文法，课上老师重点讲了2型文法，也就是上下文无关文法，对于其他几种文法提的不多，龙书上面也只讲了上下文无关文法（其他的几种文法提都没有提），课上感觉理解的还是很抽象，所以在这里再好好整理一下网上搜索到的相关概念。
Concept
0型文法（Type-0 grammars）
又称无限制文法（unrestricted grammars）。 设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，因此所有的正式文法都属于0型文法。
1型文法 （Type-1 grammars）
又称上下文相关文法（context-sensitive grammars）。 此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。
如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。
2型文法 （Type-2 grammars）
又称上下文无关文法（context-senstive grammars），它的「上下文无关」指的是每个产生式规则的展开都和上下文无关，它对应于下推自动机（pushdown automaton），是大部分编程语言的语法框架基础，语法书里展开规则基本都是上下文无关的，人类语言结构绝大部分都能表示为上下文无关文法。2型文法是在1型文法的基础上，再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。
如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。
3型文法 （Type-3 grammars）
又称正规文法（regular grammars），它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。
如有：A->a，A->aB，B->a，B->cB，则符合3型文法的要求。但如果推导为:A->ab，A->aB，B->a，B->cB或推导为:A->a，A->Ba，B->a，B->cB则不符合3型方法的要求了。具体的说，例子A->ab，A->aB，B->a，B->cB中的A->ab不符合3型文法的定义，如果把后面的ab，改成「一个非终结符＋一个终结符的形式」（即为aB）就对了。例子A->a，A->Ba，B->a，B->cB中如果把B->cB改为B->Bc的形式就对了。A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时出现在一个语法中，只能完全满足其中的一个，才能算3型文法，但是通常情况下，为了便于计算机和人们理解，我们都是采用右线性。
Summary
0 1 2 3 型都是停机可判定的 …… 因为 「递归可枚举」 的意思就是存在一个图灵机，它可以将一个文法规则能辨认的所有的字符串从短到长，一个一个不带重复的举出来。那么可以构造另一个图灵机，它一个个枚举可辨认的字符串和输入相比较，如果匹配就返回成功，如果枚举字符串长度大于输入就返回失败，总会停机的 —— 故停机可判定。
0 型文法就是图灵机停机可判定的边界，0 型文法再往上的才是停机不可判定的。
Reference
http://en.wikipedia.org/wiki/Chomsky_hierarchy
https://www.iteye.com/topic/593981