【编译原理】实验三NFA确定化和DFA最⼩化
⼀、实验标题：NFA确定化和DFA最⼩化
⼆、实验⽬的：
1. 学习和掌握将NFA转为DFA的⼦集构造法。
2. 学会编程实现等价划分法最⼩化DFA。
三、实验内容：
（⼀）NFA确定化
（1）确定NFA与DFA的存储格式。
要求为3个以上测试NFA准备好相应有限⾃动机的存储⽂件。
（2）⽤C或JAVA语⾔编写将NFA转换成DFA的⼦集构造法的程序。
（3）测试验证程序的正确性。
（4）测试⽤例参考：将下列语⾔⽤RE表⽰，再转换成NFA使⽤：
(a) 以a开头和结尾的⼩字字母串；a (a|b|…|z)*a | a
(b) 不包含三个连续的b的，由字母a与b组成的字符串；(e | b | bb) (a | ab | abb)*
(c) (aa|b)*(a|bb)*
（⼆）DFA最⼩化
（1）准备3个以上测试DFA⽂件。（提⽰：其中⼀定要有没有最⼩化的DFA）
（2）DFA⼿动完善。（状态转换映射要是满映射）
（3）⽤C或JAVA语⾔编写⽤等价划分法最⼩化DFA的程序。
（4）经测试⽆误。测试不易。可求出两个DFA的语⾔集合的某个⼦集，再证实两个语⾔集合完全相同！
四、系统设计：
1. 主程序流程
Ø 概述：通过实例化NFAtoDFA类声明测试对象test。对test初始化，选择使⽤样例1、2、3初始化test中的NFA。初始化结束后，可以多次选择打印NFA状态转换表、打印DFA状态转换表、打印minDFA状态转换表；退出后，可以选择打印对应语⾔集。输⼊len，分别输出长度≤len的NFA语⾔集、DFA语⾔集、minDFA语⾔集以验证NFA、DFA、minDFA描述了同⼀种语⾔。
Ø 流程图：
1. 算法的基本思想
Ø 概述：算法主要分为四个部分：NFA的存储、NFA转换为DFA、DFA最⼩化为minDFA 与检验NFA、DFA和minDFA描述了同⼀语⾔；v NFA转换为DFA使⽤⼦集构造算法，其中包含两个重要函数：
² closure(T)：状态集合T的闭包
² move_Tc(T,c)：状态集合T在输⼊符号为c的情况下转⼊⽬标状态的集合
v DFA最⼩化为minDFA使⽤等价划分算法。
² 获得minDFA状态集合
² 构造minDFA状态转换表minDtran
v 检验部分通过对⽐NFA、DFA和minDFA的长度⼩于等于N的语⾔集合相同证明三个状态转换图等效。
² 递归输出语⾔集合
Ø NFA的存储
从⽂件中读取⼀个NFA的要素：符号个数、符号集合、状态个数、接受状态个数、接受状态集合以及状态转换表。
状态转换表较为特殊，因为NFA的状态允许在同⼀输⼊符号下可以到达多个⽬标状态，那么完整的状态转换表则需要⼀个三维数组。在此次实验中，选⽤⼆维数组去存储状态转换表。数组内存储的是⼀个向量，在向量内存储每⼀个状态在对应输⼊符号下可能达到的状态，如下图所⽰：
在读取NFA状态转换表时，只需要获取对应数组中的向量，再遍历向量即可找到对应的状态序列。
下表中为NFA输⼊⽂件存储格式：
2 //字符个数
a b //字符集合
12 //状态个数
11 //接受状态编号
-1 -1 1,11 //从此⾏开始为状态转换表
-1 -1 2,6 //列为输⼊符号
-1 -1 3 //⾏为状态编号
4 -1 -1 //内容为对应状态下对应输⼊符号会
-1 -1 3,5 //转化到的状态列表
-1 -1 2,10
-
1 -1 7
-1 8 -1
-1 -1 7,9
-1 -1 6,10
-1 -1 1,11
-1 -1 -1
Ø ⼦集构造算法：
算法思想：为DFA构造⼀个状态转换表Dtran。DFA的每个状态是⼀个NFA的状态集合。在构造Dtran的过程中，使得DFA模拟NFA在遇到⼀个给定输⼊串时可能执⾏的所有动作。
①以NFA开始状态的闭包（状态的集合）作为DFA的开始状态。
②如果DFA的状态集合中存在⼀个状态T，T还没有模拟NFA构造过Dtran，那么对于该状态T，依次检查输⼊符号表。T在输⼊符号a下，所包含的所有NFA的状态可以到达的状态集合构成DFA状态U。
燕窝的正确炖法和吃法③检查U是否为DFA的某⼀个状态。如果不是，那么就将该状态U加⼊到DFA的状态集合中。如果是，直接进⼊下⼀步。
④构造DFA的状态转换表Dtran，即对于当前状态T，经过输⼊符号为a的转换后可以到达状态U。
⑤回到②步骤，直到DFA中所有状态都在任意⼀个输⼊符号下找到了⽬标状态，说明DFA的状态转换表Dtran构造完成。与此同时，DFA的集合也构造完成。
在构造过程中，需要使⽤以下重要的函数:
继业者战争函数名功能
closure(T)能够从T中的某个NFA状态s开始只通过ε转换到达的NFA的状态集合
move_Tc(T,c)能够从状态T中某个状态s出发通过输⼊符号c的转换到达的NFA状态的集合
文登西洋参
伪代码：
⼦集构造算法
void subt(){
标签初始化 ，标签作⽤：标记还没有构造出边的状态
初始状态设置为NFA的初始状态0的闭包T
将初始状态T加⼊Dstate，作为DFA的第⼀个状态
while(存在没有被标记的状态T){
给T加标记，说明T要作为出发状态去查找输⼊符号的跳转状态
对于状态集合T，在输⼊符号为charSet[i]下，跳转到的状态集合U
for(对于任意⼀个输⼊符号a){
U = closure_T(moveTc(T,a));
if(U不在Dstate状态集合中){
if(U包含NFA中的接受状态){
将U设置为接受状态
浪漫小镇
}
将U加⼊DFA的状态集合
}
对当前状态T和输⼊符号a构造状态转换到达状态U
}
}
构造完毕，将DFA状态数⽬设置为当前状态数⽬
}
closure(T)算法
__int64 closure_T(__int64 T){宫保鸡丁的配料表
将T中所有状态压⼊stateStack栈中
将closure(T)初始化为T，即需要包含⾃⾝状态
while(stateStack栈不为空){
将栈顶状态t弹出
for(每个满⾜如下条件的u：从t出发有⼀个标号为空的转换到达u){
if(u不在closure(T)中){
将u加⼊closure(T)中；
将u压⼊stataStack栈中；
}
}
返回新的状态集合
}
Ø 等价划分算法：
算法思想：将⼀个DFA的状态集合划分成多个组，每个组中的各个状态之间互相不可区分。然后将每个组中的状态合并成minDFA的⼀个状态。算法在执⾏过程中维护了状态集合的⼀个划分，划分中每个组内各个状态尚不能区分，但是来⾃任意两个集合的不同状态是可以区分的。当任意⼀个组都不能被分解为更⼩的组的时候，这个划分就不能再⼀步精化，这样就可以得到minDFA。
算法步骤：
①将DFA的所有状态划分为两个集合：不包含接受状态的集合T1，包含接受状态的集合T2；以这两个为基础，进⾏集合划分。
②对于现有状态集合中任意⼀个状态集合T，对于⼀个输⼊符号a。新建状态集合数组U，数组对应长度为当前DFA状态个数。设⽴flag标识，为0表⽰不需要再划分。
③记录T中第⼀个状态经过a到达的状态x。依次检查T中第⼆个、第三个状态.....；如果第i个状态经过a到的状态不为x⽽为y，那么表⽰当前划分集合仍需要划分，将flag设置为1，同时将第i个状态从状态集合T中删除。同时将状态i加⼊⼀个y对应的U数组中的集合。如果第j个状态进过a到达的状态也为y，就将状态j也加⼊到y对应的U数组中的集合。
④将新产⽣的划分U加⼊到原来的划分T中；
⑤回到第⼆步执⾏，直到flag为0，说明不需要再进⾏划分，minDFA状态集合构造完毕。
void minDFA(){
初始化分为接受状态组和⾮接受状态组
对于当前每⼀组进⾏划分
while(flag为1，仍有组需要划分){
flag = 0;
数组goalSet（与当前minDFA分组数⽬相同）记录组别对应产⽣的新组
for(对于当前分组中的所有状态){
消防安全制度灭火和应急疏散预案for(对于每⼀个输⼊符号){
if(i为组内第⼀个状态){
记录i经过符号j到达状态组T
}
el if(如果i经过符号j到达的状态组为Q){
flag=1;
将i从状态组T中删除
将i加⼊到Q对应的goalSet中
}
}
}
将goalSet中不为空的组并⼊旧组
当前minDFA状态数⽬等于原本状态数⽬+新状态数⽬汽车打蜡
}
画口罩简笔画划分结束，构造状态转换表
}
Ø 验证算法：
