文法
一个文法可以用一个四元来定义，G = {Vt，Vn，S，P}
Vt：一个非空有限的符号集合，它的每个元素称为终结符号;
Vn：一个非空有限的符号集合，它的每个元素称为非终结符号，并且Vt∩Vn=Φ;
S∈Vn，称为文法G的开始符号;
P是一个非空有限集合，它的元素称为产生式;
产生式是指，其形式为α→β，α称为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α、β∈(Vt∪Vn)*，α≠ε，即α、β是由终结符和非终结符组成的符号串;
开始符S必须至少在某一产生式的左部出现一次;
文法可推导的语言标记为L(G);
根据对产生式所施加的限制的不同，把文法分成0型、1型、2型和3型四种类型
0型文法要求至少含有一个非终结符，基本没有什么限制，一个非常重要的理论结果是：0型文法的能力相当于图灵机 1型文法也叫上下文有关文法，对应于线性有界自动机，要求每个产生式α→β，都有|β|>=|α|，|β|指长度； 2型文法也叫上下文无关文法，对应于下推自动机，要求在1型文法的基础上，再满足：每一个α→β都有α是非终结符; 3型文法也叫正则文法，它对应于有限状态自动机。它是在2型文法的基础上满足：A→α|αB（右线性）或A→α|Bα（左线性)。 1型文法是0型文法的一个子集，2型文法是1型文法的一个子集，,3型文法是2型文法的一个子集
3型文法(正则文法)与正则表达式(Regular Expression)是等价的，任意一个正则文法总是可以转化成一个等价的正则表达式。
同时正则表达式与有限自动机是等价的。
能由有限自动机识别的语言，必然可以用正则表达式来表示，而一个用正则表达式表示的语言一定可以用一个有限自动机来识别。
有限状态自动机
有限自动机分为多种最常见的是：确定型有限自动机(DFA)和非确定型有限自动机(NFA)两种;
DFA的文法描述是：G = {S，ε, f，S0，Z}NFA的文法描述是：M = {S，ε, f，S0，Z}S：一个非空有限的输入符号集合；S：一个非空有限的输入符号集合；ε：使状态改变的输入符号集合；ε：使状态改变的输入符号集合；f：映射；f：映射；S0：初始状态；S0：初始状态集合；Z：终止状态；Z：终止状态； f(S,a)=G的描述是：初始S状态再输入a的条件下转化到G状态：每一个NFA都可以转化为一个DFA如图：参考： http://www.cnblogs.com/longhuihu/p/4128203.html
转载于:https://www.cnblogs.com/pumpkinSpeakness/p/4161710.html
相关资源：AOC E960sn程序 715G5265-M01-000-004Q