本程序的基本數(shù)據(jù)結(jié)構(gòu)是string類型的數(shù)組，用于儲存劃分的子集，而子集中的元素的鄰接點與權(quán)值都在edge結(jié)構(gòu)體數(shù)組中存儲。 把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的. 算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非終態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己。 1.構(gòu)造狀態(tài)的一初始劃分：終態(tài)kt 和非終態(tài)K- kt兩組(group) 2.對∏施用過程PP 構(gòu)造新劃分∏new 3.如∏new =∏,則令 ∏final=∏ 并繼續(xù)步驟4，否則∏:=∏ new重復(fù)2 . 4.為∏final中的每一組選一代表，這些代表構(gòu)成M’的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M’中有一轉(zhuǎn) 換f’(k,a)=rM’ 的開始狀態(tài)是含有S0的那組的代表 M’ 的終態(tài)是含有F的那組的代表 5.去掉M’中的死狀態(tài). 輸入文本格式樣例： 0 a 1 1 a 2 2 a 2 2 d 3 1 d 3 3 d 3 3 a 2 # 123 0 ad