文法是一个四元组：G = {VT,VN,S,P}
其中VT是一个非空有限的符号集合，它的每个元素成为终结符号。VN也是一个非空有限的符号集合，它的每个元素称为非终结符号，并且VT∩VN=Φ。S∈VN，称为文法G的开始符号。P是一个非空有限集合，它的元素称为产生式。所谓产生式，其形式为α→β，α称为产生式的左部，β称为产生式的右部，符号“→”表示“定义为”，并且α、β∈(VT∪VN)*，α≠ε，即α、β是由终结符和非终结符组成的符号串。开始符S必须至少在某一产生式的左部出现一次。另外可以对形式α→β，α→γ的产生式缩写为α→β|γ，以方便书写。
注：一般以大写字母表示非终结符，以小写字母表示终结符。
著名语言学家Noam Chomsky(乔姆斯基)根据对产生式所施加的限制的不同，把文法分成四种类型，即0型、1型、2型和3型。
本质上形式化语言----回到数学表达式
有限状态自动机 FSA finite state automata
注：说明一点，只要是有限状态自动机，则必定符合3型文法，且可用正则表达。
一个确定的有限状态自动机M(记做DFA)是一个五元组：M=(∑,Q,q0,F,δ)
其中：
(1) Q是一个有限状态合集【全部的组合情况】
(2) ∑是一个字母集，其中的每个元素称为一个输入符号【词典或者基本语素】
(3) q0∈Q，称为初始状态
(4) F∈Q，称为终结状态集合
(5) δ是一个从Q×∑(Q与∑的笛卡尔积)到Q的单值映射：（单值映射是f(x)=y，在x确定时，得到的y唯一）【笛卡尔积】
δ(q,a)=q* (q,q*∈Q, a∈∑)
以上式子表示当前状态为q，输入符号a时，自动机将转换到下一个状态q*，q*称为q的一个后继。
若Q={q1,q2,...,qn },∑={a1,a2,...,an}，则(δ(qi,aj)) n×m是一个n行m列矩阵，称为DFA的状态转换矩阵，或称转换表。
有限状态自动机可以形象地用状态转换图表示，举例如下：
DFA M=({S,A,B,C,f},{1,0},S,{f },δ)
其中：δ(S,0)=B, δ(S,1)=A, δ(A,0)=f, δ(A,1)=C, δ(B,0)=C, δ(B,1)=f, δ(C,0)=f , δ(C,1)=f
则对应的状态转换图如下所示：
其中圈表示状态结点，双圈表示终结状态结点，而边表示状态的转换，代表映射。边上的符号表示此转换需要输入的符号，代表映射的输入。
对于∑上的任何字符串w∈∑*，若存在一条从初始结点到终态结点的路径，在这条路径上的所有边的符号连接称的符号串恰好是w，则w被DFA所识别(或接受、读出)。DFA所能识别的符号串的全体记为L(M)，称为DFA所识别的语言。
唯一性
对于任意给定的确定有限状态自动机都能找到一个与之计算能力等价的最小确定有限状态自动机，简称最小自动机。该最小自动机中状态的数量等于能识别相同语言的等价类自动机中等价关系的数量，我们可以称最小自动机和等价类自动机“实际上”是相等的，也就是同构。非正式的说法是：对于最小自动机上的任意状态都可以通过一个同构函数变换成等价类自动机上的一个状态。
能识别一个正则语言的等价类自动机是唯一的，因此能识别该语言的最小自动机也是唯一的。
NFA介绍
之前介绍的是确定的有限自动机，即一个状态对于待定的输入字符有一个确定的后继状态。而当一个状态对于特定的输入字符有一个以上的后继状态时，我们称该有限自动机为非确定有限自动机(记做NFA)，其形式定义也是M=(∑,Q,q0,F,δ)，且前面的字符定义均和DFA相同，但是δ：Q×∑对应所有Q的任意子集。
在NFA中能够识别的路径与DFA中定义也相同。
对任何一个NFA，都存在一个DFA*使L(M*)=L(M)，这时我们称M*与M等价。构造与M等价的M*的基本方法是让M*的状态对应于M的状态集合。即如果δ(q,a)={q1,q2,...,qn}，则把{q1,q2,...,qn}看作M*的一个状态，即M*中的状态集合Q*的一个元素。
有限状态转换机(FST finite state transducer )
如果把FSA中弧上的字母换成两个字母，一个称为输出字母、一个称为输入字母，这样得到FSA就是一个有限状态转换机(Finite State Transducer)。
有限状态转换机(FST)
一个有限状态转换机M是一个五元组(Q,Σ, q0, F, δ).
有限个状态组成的状态集: Q
有限个复杂字母组成的字母表: Σ，其中每个复杂字母由一个输出字母和一个输入字母组成，o:i
一个开始状态q0
终止状态的集合F⊆Q
状态转移函数δ(q,o:i): Qx（Σ:Q）
有限状态转换机建立起两个字符串间的联系。
有限状态转换机(FST)
FST有两条输入带子
FST作为识别装置(recognizer)
给定一对字符串，FST拒绝或接受
FST作为生成装置(generator)
生成一对字符串
FST作为翻译装置(translator)
给定一个字符串，生成另一个字符串
构建形态分析器所需要的资源
1. 词典(lexicon)
词干和词缀
词干和词缀的基本信息(如:词干的类别)
2. 形态知识(morphotactics)
语素间的顺序关系
那一类语素可以和那一类语素组合
(例如：名词后面可以加一个复数语素)
3. 正字规则(orthographic rule or spelling rule)
两个语素组合时应进行怎样的变化
(如:把y改写为i加es)
Finite State Automata in Lucene
FSA construction linear-time minimal,deterministic 线性构造时间开销、最小、确定状态
Linear algorithm form sorted input
Active path（ states that still can change）
States dictionary（nodes that will never change）
FSA 基于弧而不是状态
