乔姆斯基文法分类

  终结符，通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。不是终结符的都是非终结符。非终结符可理解为一个可拆分元素，而终结符是不可拆分的最小元素。如：有α → β ，则α 必然是个非终结符。一般书上把非终结符用大写字母表示，而终结符用小写字母表示。识别符号就是开始符。由文法产生语言句子的基本思想是：从识别符号开始，把当前产生的符号串中的非终结符号替换为相应规则右部的符号串，直到最终全由终结符号组成。这种替换过程称为推导或产生句子的过程，每一步成为直接推导或直接产生。

(非终结符:A,B,C,D,终结符:a,b,c,d)  
  0型文法,产生式左右部可以使用"非终结符"和"终结符"随意组合,但左部不能为空,如DAaBb->CcdD;  
  1型文法,在0型文法的基础上,要求右部的符号长度大于左部(空除外),如AaBb->CcddDd
  1<=|AaBb|<=|CcddDd|
  2型文法,在1型文法的基础上,要求左部必须由非终结符号组成,如AB->CcdddDd  
  3型文法,在2型文法的基础上,产生式必须型如:A->Aa|a或A->aA|a,比如:A->AA,A->aa,这些都不是

3型文法也许是大家最难理解的，下面为大家举几个例子来说明：

3型文法
　　3型文法也叫正规文法，它对应于有限状态自动机。它是在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型文法。
　　注意：上面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符