1. DFA与NFA的定义
(1) 概述
有穷自动机又称有限自动机，是识别正规文法的语言以及其所表示的集合，包括
DFA(Deterministic Finite Automata)确定的有穷自动机和NFA(Nondeterministic Finite Automata)不确定的有穷自动机。
(2) DFA
一个确定的有穷自动机M是一个五元组：
M = ( K , ∑ , f , S , Z ) M = (K, \sum,f,S,Z)M=(K,∑,f,S,Z)
(1) K KK 是一个有穷集，它的每个元素称为一个状态
(2)∑ \sum∑ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称其为输入符号表
(3)f ff是转换函数，是K × ∑ → K K \times\sum \to KK×∑→K上的映像。例如 f ( k i , a ) = k j ( k i , k j ∈ K ) 表 示 在 状 态 k i 输 入 一 个 字 符 a 即 转 换 到 状 态 k j f(k_{i},a)=k_{j}(k_{i},k_{j}\in K) 表示在状态k_{i}输入一个字符a即转换到状态k_{j}f(ki,a)=kj(ki,kj∈K)表示在状态ki输入一个字符a即转换到状态kj
(4)S ∈ K \in K∈K是唯一的初态
(5)Z ∈ K \in K∈K是唯一的终态
一个DFA可表示成状态图
(3) NFA
一个不确定的有穷自动机M MM是一个五元组：
M = ( K , ∑ , f , S , Z ) M = (K,\sum,f,S,Z)M=(K,∑,f,S,Z)
(1) K KK 是一个有穷集，它的每个元素称为一个状态
(2)∑ \sum∑ 是一个有穷字母表,它的每个元素称为一个输入符号
(3)f ff是转换函数，是K × ∑ ∗ → 2 k K \times\sum^* \to 2^kK×∑∗→2k上的映像,其中2 k 2^k2k表示K KK的幂集(∑ ∗ = ∑ 0 ∪ ∑ 1 ∪ ⋯ ∪ ∑ n 其 中 ∑ 0 = ε , ε 是 空 串 \sum^*=\sum^0\cup\sum^1\cup\dots\cup\sum^n其中\sum^0=\varepsilon,\varepsilon是空串∑∗=∑0∪∑1∪⋯∪∑n其中∑0=ε,ε是空串)
(4) S ∈ K S\in KS∈K，是一个非空初态集
(5)Z ∈ K Z\in KZ∈K，是一个非空终态集
一个NFA也可表示成状态图
2. NFA转换成等价的DFA——子集法
(1) 依据：
设L为一个NFA接受的集合，则存在一个接受L的DFA
(2) 子集法：
首先定义两个运算：
1> ε − c l o s u r e ( I ) \varepsilon-closure(I)ε−closure(I)：ε 闭 包 , 状 态 集 I 中 的 任 意 状 态 S 经 任 意 条 ε 弧 能 够 到 达 的 状 态 的 集 合 \varepsilon闭包,状态集I中的任意状态S经任意条\varepsilon弧能够到达的状态的集合ε闭包,状态集I中的任意状态S经任意条ε弧能够到达的状态的集合
2>m o v e ( I , a ) : 状 态 集 合 I 的 a 弧 转 换 ， 指 状 态 集 合 I 中 任 意 状 态 能 经 过 一 个 a 弧 到 达 的 状 态 的 全 体 move(I,a):状态集合I的a弧转换，指状态集合I中任意状态能经过一个a弧到达的状态的全体move(I,a):状态集合I的a弧转换，指状态集合I中任意状态能经过一个a弧到达的状态的全体
思路 ：
DFA的每个转换都是确定的，而NFA中包含空串ε \varepsilonε,导致了它不确定。我们要做的就是合并空串ε \varepsilonε所导致的的等价状态从而消除空串。所谓等价状态即能通过若干个ε \varepsilonε连接的状态。如下图所示，状态0经过一条ε \varepsilonε到达状态1，经过两条ε \varepsilonε到达状态2，因此{0,1,2}等价,最后会合并成一个状态。而求某个状态 t tt 的等价状态就是在做ε − c l o s u r e ( t ) \varepsilon-closure(t)ε−closure(t)运算。注意：由于NFA中每个状态允许存在多条ε \varepsilonε出弧，且可能之间还存在非ε \varepsilonε弧。因此，NFA中的每个状态会重复出现在多个等价状态中。不容易直接通过求等价状态(结点)来求DFA
我们知道，由弧连接的两个结点都是状态，可以看作图。对于图的构建来说，只需找出一个结点然后通过它的出弧找到其他结点(这个过程即m o v e ( K , ∑ ) move(K,\sum)move(K,∑)运算),并对这些结点递归处理即可找到所有的结点，类似于图的广搜。对于NFA来说，我们可以先求出初始状态的等价状态ε − c l o s u r e ( S ) \varepsilon-closure(S)ε−closure(S)即第一个结点,然后通过它的出弧来找到其他状态，从而构建DFA。
第一步：求初始状态的等价状态 T 0 = ε − c l o s u r e ( S ) T_{0} = \varepsilon-closure(S)T0=ε−closure(S)
第二步: 找到T 0 T_{0}T0中所有出弧以及对应的状态(以下仅以出弧a为例)T e m p = m o v e ( T 0 , a ) ( a ∈ ∑ ) Temp = move(T_{0},a) (a\in \sum)Temp=move(T0,a)(a∈∑)。由于T 0 T_{0}T0存在一条出弧a到达Temp，因此Temp必须作为一个状态。根据等价思想，可令T 1 = ε − c l o s u r e ( T e m p ) T_{1} = \varepsilon-closure(Temp)T1=ε−closure(Temp),即Temp的等价状态T 1 T_{1}T1是NFA中新的状态T 0 与 T 1 之 间 的 映 射 关 系 为 D ( [ T 0 ] , a ) = T 1 T_{0}与T_{1}之间的映射关系为D([T_{0}],a) = T_{1}T0与T1之间的映射关系为D([T0],a)=T1
第三步：将求出的新状态再重复步骤二。直到得到的状态均已存在。
最终得到新状态：T 0 、 T 1 、 T 2 、 T 3 … T n T_{0}、T_{1}、T_{2}、T_{3}\dots T_{n}T0、T1、T2、T3…Tn以及之间的映射关系D ( [ T 0 ] , a ) = T 1 、 D ( [ T 0 ] , b ) = T 2 、 D ( [ T 2 ] , a ) = T 3 、 … D ( [ T n ] , a ) = T n D([T_{0}],a) = T_{1}、D([T_{0}],b) = T_{2}、D([T_{2}],a) = T_{3}、\dots D([T_{n}],a) = T_{n}D([T0],a)=T1、D([T0],b)=T2、D([T2],a)=T3、…D([Tn],a)=Tn
即
K = { T 0 、 T 1 、 T 2 、 T 3 … T n } K=\{ T_{0}、T_{1}、T_{2}、T_{3}\dots T_{n}\}K={T0、T1、T2、T3…Tn}
f = D f=Df=D
∑ = ∑ \sum=\sum∑=∑
S = T 0 S = T_{0}S=T0
Z = T n Z =T_{n}Z=Tn
则有M D F A = ( { T 0 、 T 1 、 T 2 、 T 3 … T n } , ∑ , D , T 0 , T n ) M_{DFA} =(\{ T_{0}、T_{1}、T_{2}、T_{3}\dots T_{n}\},\sum,D,T_{0},T_{n})MDFA=({T0、T1、T2、T3…Tn},∑,D,T0,Tn)