NFA 转换为 DFA 文档
小组成员：紫林
概念
DFA 又被称为确定的有穷自动机，在当前状态下读入一个字符，仅有一个或者没有后继
状态。
NFA 又被称为不确定的有穷自动机，在当前状态下读入一个字符，可能会出现多个后继
状态。
表示方法
NFA 与 DFA 可以用矩阵表示，这样可以快速访问给定状态下输入确定字符后出现的转换
状态表。状态占行，输入字符占列。分析可以得出，NFA 中的后继状态可能是一个状态集，
而 DFA 的状态一定是单一的一个状态。从而可以得出 NFA 向 DFA 转换的关键是建立 NFA
中状态表与 DFA 中单一状态的映射关系。
转换规则
将 NFA 转换为 DFA 应用空闭包规则。
假设 I 是 NFA M 状态集 K 的一个子集（即 I∈K），则定义 空-closure（I）为：
（1） 若 Q∈I，则 Q∈空-closure（I）；
（ 2 ） 若 Q∈I ， 则 从 Q 出 发 经 过 任 意 条 空 弧 而 能 到 达 的 任 何 状 态 Q’ ， 则 Q’∈ 空 -
closure（I）。
状态集空-closure（I）称为状态 I 的空闭包。
定义 Ia＝空-closure（J），其中 J 是所有从空-closure（I）出发，经过一条 a 弧而到达的状
态集，即 J=move(T1,a)。
NFA 确定化的实质是以原有状态集上的子集作为 DFA 上的一个状态，将原状态间的转换为
该子集间的转换，从而把不确定有限自动机确定化。
NFA 到 DFA 的构造方法
1.空-closure(s) 能够从 NFA 的状态 S 开始只通过 0 转换到达的 NFA 的状态集合
2.空-closure(T) 能够从 T 中的某个 NFA 状态 s 开始只通过 0 转换到达的 NFA 的状态集合
3.move(T,a) 能够从 T 中某个状态 s 触发只通过标号为 a 的转换转换达到的 NFA 状态集合
/**子集构造法*/
NFA-DFA-CONVERT(nfa, dfa)
s0 -> nfa 的开始状态
U -> 空-closure(s0)
push U into dfa without mark
while ( T -> find one in dfa without mark){
mark T;
for(every possible intput a)
U' -> 空-closure(move(T, a))
if(U' is not in dfa)
push U' into dfa without mark
