自动机
自动机是一种理想化的“机器”，它只是抽象分析问题的理论工具，并不具有实际的物质形态。它是科学定义的演算机器，用来表达某种不需要人力干涉的机械性演算过程。根据不同的构成和功能，自动机分成以下4种类型：有限自动机（finite automata, FA）、下推自动机（pushdown automata, PDA）、线性界限自动机（linear-bounded automata）和图灵机（Turing machine）。
有限自动机
有限自动机又分为确定性有限自动机（definite automata, DFA）和不确定性有限自动机（non-definite automata, NFA）两种。
确定性有限自动机
（确定性有限自动机） DFA M是一个五元组：M＝（Σ，Q，δ，q0，F）
其中，Σ是输入符号的有穷集合；Q是状态的有限集合；q0∈Q是初始状态；F是终止状态集合，F⊆Q；δ是Q与Σ的直积Q×Σ到Q（下一个状态）的映射，它支配着有限状态控制的行为，有时也称为状态转移函数。
上图是DFA的原理示意图。其含义是：处在状态q∈Q中的有限控制器从左到右依次从输入带上读入字符。开始时有限控制器处在状态q0，输入头指向Σ*中一个链的最左符号。映射δ（q，a）＝q′（q，q′∈Q,a∈Σ）表示在状态q时，若输入符号为a，则自动机M进入状态q′并且将输入头向右移动一个字符。
映射与状态转换图
映射δ（q，a）＝q′（q，q′∈Q,a∈Σ）
为了明确起见，终止状态用双圈表示，起始状态用有“开始”标记的箭头表示。如:
DFA M示例：
上图的例子中,Σ输入符号的有穷集合为0和1,Q状态的有限集合为{q1,q0},初始状态q0为q1,F终止状态集合为{q0},δ状态转移方程为 q1(0)->q0 、q1(1)->q1 、q0(1或0)->q0
有限自动机所接受的语言
如果存在一个状态p，有p∈δ（q0， x）且p∈F，则称句子x被NFA M所接受。被NFA M接受的所有句子的集 合称为NFA M定义的语言，记作T（M）：
T(M) = {x | p∈δ(q0,x) 且 p∈F }
因而有限自动机可以用来检验句子是否合法
不确定性有限自动机 NFA M
NFA M是一个五元组：
M＝（Σ,Q,δ,q0，F）
其中，Σ是输入符号的有穷集合；Q是状态的有限集合；q0∈Q是初始状 态；F是终止状态集合，F⊆Q；δ是Q与Σ的直积Q×Σ到Q的幂集2Q的映 射。 NFA与DFA的重要区别是：在NFA中δ（q, a）是一个状态集合，而 在DFA中δ（q, a）是一个状态。根据定义，对于NFA M有映射： δ（q, a）＝{q1，q2，…，qk}，k≥1 其含义是：NFA M在状态q时，接受输入符号a时，M可以选择状态 集q1，q2，…，qk中的任何一个状态作为下一个状态，并将输入头向右 边移动一个字符的位置。
NFA接受的语言
如果存在一个状态p，有p∈δ（q0， x）且p∈F，则称句子x被NFA M所接受。被NFA M接受的所有句子的集 合称为NFA M定义的语言，记作T（M）：
T(M) = {x | p∈δ(q0,x) 且 p∈F }
有定理
设L是被NFA所接受的语言，则存在一个DFA，它能够接受L。
正则文法与有限自动机
因为正则文法是产生式模型，不能很好验证句子是否符合文法规则，通过将正则文法转变成有限自动机形式可以很好地解决这类问题。
若G＝（VN，VT，P，S）是一个正则文法，则存在一个 FA M＝（Σ，Q，δ,q0，F），使得T（M）＝L（G）。 根据这个定理，可以用以下方法由给定的正则文法G＝（VN，VT， P，S）构造FA M。具体步骤如下：
（1）令Σ＝VT，Q＝VN∪{T}，q0＝S，其中T是一个新增加的非终 结符；
（2）如果在P中有产生式S→ε(空)，则F＝{S，T}，否则F＝{T}；
（3）如果在P中有产生式B→a(终止符)，B∈VN，a∈VT，则T∈δ（B, a）；
（4）如果在P中有产生式B→aC(终止符与非终止符)，B，C∈VN，a∈VT，则C∈δ（B, a）；
（5）对于每一个a∈VT，有δ（T, a）＝∅。
给定正则文法G＝（VN，VT，P，S），其中， VN＝{S，A}， VT＝{0,1} P：S→0 A A→1 S A→0 构造与G等价的NFA：
（1）设NFA M＝（Σ，Q，δ，q0，F），根据上述构造步骤有： Σ＝VT＝{0,1}， Q＝VN∪{T}＝{S，A，T}，q0＝S， F＝{T}
（2）映射δ为
δ（S,0）＝{A} （因为有规则S→0 A）
δ（S,1）＝∅ δ（A,0）＝{T} （因为有规则A→0）
δ（A,1）＝{S} （因为有规则A→1 S）
δ（T,0）＝∅ δ（T,1）＝∅
（3）该NFA M的状态转换图可以由上面的映射关系构成，如下图所示。
上下文无关文法与下推自动机
下推自动机（PDA）可以看成是一个带有附加下推存储器的有限自 动机，下推存储器是一个堆栈（stack）。其原理示意图如图所示。
不确定的下推自动机（PDA）可以表达成一个七元组：
M＝（Σ，Q，Γ，δ，q0，Z0，F）
其中，Σ是输入符号的有穷集合；Q是状态的有限集合；Γ为下推存储器 符号的有穷集合；q0∈Q是初始状态；Z0∈Γ为最初出现在下推存储器顶 端的开始符号；F⊆Q是终止状态集合；δ是从Q×（Σ∪{ε}）×Γ到Q×Γ* 的子集的映射。映射关系δ：
网友评论