文法：
认识终结符和非终结符
终结符 非终结符
（小写，不可再分元素） （大写，可再分元素）
例如：
有文法G2[S]为
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
这里S为开始符，S,A,B为非终结符，而p,q,a,b,c,d为终结符
注意：终结符不能单独在左边，即a->b 这是错误的。a不能单独在左边；
文法类型：
* 0型文法
* 1型文法
* 2型文法
* 3型文法
0型文法：
设（Vn,Vt,P,S），如果它的每个产生式 α->β 是这样的一种结构：
α∈（Vn ∪ Vt）* '（且至少含有一个非终结符)'，而β∈（Vn ∪ Vt）*.则G是一个0型文法。
（
()*称为闭包，
Vn:非终结符集合，
Vt:终结符集合，
P:推导式集合，
S:开始符
）
0型文法也称 “ 短语文法 ”。一个非常重要的理论结果是：0型文法相当于图灵机（Turing）。
或者说，任何0型文法语言都是递归可枚举的，反之，递归可枚举集必定是一个0型文法；
0型文法是这几类文法中，限制最少的一个。所以我们在试题中见到的，至少是0型文法
例如上面的G2[S]文法
S,A,B p,q,a,b,c,d都属于（Vn ∪ Vt）*
Sa,BacB，Ab,AB,SA,abc组合元素也属于（Vn ∪ Vt）*
一个串的所有元素都∈（Vn ∪ Vt），不管这个串多长，它都属于（Vn ∪ Vt）*
所以:G2[S]文法属于0型文法.
1型文法：
1型文法也叫上下文有关文法，此文法对应于线性有界自动机。它是在0型文法的基础上每一个α->β,
都有 |α|->|β| ，这里的|β|表示的是β的长度。
注意：虽然要求 |β| >= |α|,但有一特例，α-> 也满足1型文法。
例如 A->Ba , 则|β|=2,|α|=1符合1型文法要求。反之，如aA->a，则不符合1型文法。
2型文法：
2型文法也叫上下文无关文法，它对应于下推自动机。2型文法是在1型文法的基础上，再满足：
每一个 α->β 都有α是非终结符。
例如A->Ba，符合2型文法要求。
如：Ab->Bab 虽然符合1型文法要求，但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符，如何AB则为一个非终极符
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型文法的要求了。
要不全部统一右线性，要不全部统一左线性，才符合3型文法的要求；
左右线性混合不符合3型文法的要求
3型文法 （含于） 2型文法 （含于） 1型文法 （含于） 0型文法
例题：
有文法G为：
A->∑|aB
B->Ab|a
请判断文法G属于哪一类文法？
首先看到 |，先把文法拆分出来,得到
A->∑ A->aB
B->Ab B->a
从0型文法开始算起；
所以文法G属于2型文法，不属于3型文法
例题：
在文法G=（Vn,Vt,P,S）,G=（{S,A,B},{0,1},P,S）中，P的生成式有:
S->0A
S->0
S->A0
S->0A0
这时，G属于3型文法吗？
答案：不属于3型文法。S->0A0 既不属于右线性，也不属于左线性
如何判断一个串是否为某个文法的句型
两种判断方法：构造推导树和直接进行推导。
例题：
已知文法G[S]:S->A0|B1，A->S1|1，B->S0|0;该文法属于乔姆斯基定义的___文法，它不能产生的串___;
(1)A.0型 B.1型 C.2型 D.3型
(2)A.0011 B.1010 C.1001 D.0101
分析：
此文法的推导式有：
S->A0
S->B1
A->S1
A->1
B->S0
B->0
这些推导式完全与：A->α|Bα (左线性）形式相符，所以此文法是3型文法
S为开始符,所以从S开始推导
（直接推导）由于：
S->A0->S10->A010->1010
S->B1->S01->A001->1001
S->B1->S01->B101->0101
此文法不能产生的串为：0011
构造推导树
