文法
终结符：不能单独出现在推倒式的左边。具有原子性，不可在分。
非终结符：可以拆分的元素。
一般用大写代表非终结符，用小写字母代表终结符。
文法类型：
0型文法：G=（Vn，Vt，P，S），如果每个产生式α→β都符合，a∈（VnUVt）*且至少含有一个非终结符，β∈（VnUVt）*，则G是一个0型文法。
0型文法也成为短语文法。
0型文法的能力相当于图灵机（Truing）。任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。
PS：
Vn：非终结符的集合
Vt：终结符的集合
P：推导式的集合
S：推导符
（）*递包的含义是用括号内任意的元素进行组合拼接起来的一个串
1型文法：
0型文法是基础，在0型文法α→β的基础上。有|β|>=|α|。|β|表示β的长度。
又称为：上下文有关文法。
此文法对应于线性有界自动机。
特例：α→ξ（空） 也满足1型文法。
2型文法：
在1型文法的基础上，每一个α→β都有α是非终结符。
又称为：上下文无关文法。
3型文法：
3型文法是在2型文法的基础上。A→α|αB（右线性）或A→α|Bα（左线性）。“|”为或的意思。
必须注意：它的规则只能符合前面的或者后面的，如果同时A->Ba,B->aB。则不符合3型文法。
即要不都符合左线性，要不就都符合右线性。不能两个掺和着。
又称为：正规文法