文法（形式语法）的定义 G = (N,∑,P,S) 参考自然语言处理一--基本概念
正则文法：如果文法G的重写规则P中所有规则都满足：
A→Bx,或A→x,其中A,B∈N，x∈∑ （解释：A,B属于非终结符，x属于终结符，文法的推导规则中，终结符都只在一侧。）
那么称文法G为正则文法，也叫3型文法。
例如：
G = (N,∑,P,S)，其中N=(S,A,B),∑={a,b}
P:S→aA
或者P:A→aA
或者P:A→bbB
都是正则文法。
上下文无关文法：如果文法G的重写规则P中所有规则都满足：
A→a, A∈N，a∈（N,∑）* （解释：A属于非终结符，a属于非终结符与终结符的任意组合）
例如：
G = (N,∑,P,S)，其中N=(S,A,B,C),∑={a,b,c}
P:S→ABC
或者P:A→BA|c
或者P:A→AC|AcB
都是上下文无关文法。
上下文有关文法:如果文法G的重写规则P中所有规则都满足：
αAβ→αγβ，A∈N, α β γ∈（N,∑）* （解释：A属于非终结符，αβγ属于非终结符与终结符的任意组合，并且γ至少包含一个字符。）
无约束文法：如果文法G的重写规则P中所有规则都满足：
α→β，α∈（N,∑）+, β∈（N,∑）* （解释：A属于非终结符与终结符的非空集合，αβγ属于非终结符与终结符的任意组合。）
正则文法（RG）⊆上下文无关文法（CFG）⊆上下文有关文法（CSG）⊆无约束文法（PSG）
自动机：是指抽象分析问题的理论工具，并不具有实际的物质形态。是指一种理想化的“机器”。它是科学定义的演算机器，用来表达不需要人力干涉的机械性演算过程。