一、试验名称
确定有穷自动机的最小化
二、试验目标
- 输出DFA，输入等价的状态数起码的DFA
- 实现子集划分算法
- 输出和输入均以定义的模式
三、试验原理
1、DFA的定义
一个确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中
a. K是一个有穷集，它的每个元素称为一个状态；
b. E是一个有穷字母表，它的每个元素称为一个输出符号；
c. f是转换函数，是K×E->K上的映像，即，如f(ki,a)=kj(ki∈K,kj∈K)就意味着，以后状态为ki，输出字符为a时，将转换到下一状态kj，咱们把kj称作ki的一个后继状态；
d. S∈K，是惟一的一个初态；
e. Z蕴含于K，是一个终态集，终态也称可承受状态或完结状态。
2、无用状态
所谓有穷自动机的无用状态，是指这样的状态：从该自动机的开始状态登程，任何串也不能到达的那个状态。或者从这个状态没有通路达到状态。
3、状态等价条件
a.一致性条件——状态s和t必须同时为可承受状态或不可承受状态
b.蔓延性条件——对于所有输出符号，状态s和状态t必须转换到等价的状态里。
四、试验思路
1、输出
依据试验要求，以DFA的定义模式输出，即输出M=(K,E,f,S,Z)，其中f另外输出。采纳putin作为输出函数，首先输出定义模式，用split函数依照’}‘进行宰割，再依照’}’宰割。最初对失去的二维列表zanshi1中的元素进行输入，失去K,E,S,Z。再输出f中弧的条数，顺次输出弧。
2、move算法
move算法与NFA的确定化里的算法一样，在这里为了求某一子集通过弧达到什么子集而应用move算法。思路是：建设一个新列表寄存move算法产生的状态汇合，若f中的弧的输出符号为a或者b，求通过紧跟a或者b的下一个状态，将这些状态放于新列表中。
3、子集划分算法
定义operation()函数为子集划分算法函数，具体执行步骤如下：
a.将K中的状态集分为两种：终态集和非终态集，存于KK中，KK寄存最终划分后失去的汇合。
b.设立循环条件，子集划分算法划分最细的状况是每个状态都为一个子集，所以以此作为循环条件。若KK中汇合个数不等于K中状态个数，则持续循环。
c.设立标记位llag=0用来决定是否跳出循环，每不执行一次划分算法则llag加1，若最终llag等于KK长度，阐明此次循环没有子集划分，则阐明划分结束，退出循环。
d.对KK中的汇合顺次进行操作，判断他们进过move算法失去的汇合是否是KK中已有的汇合，若是则不执行划分，否则执行划分算法。
e. 若执行划分算法，则先算出汇合中首个状态的move算法失去的汇合属于哪个已知汇合，再对其余状态进行同样操作，和首个状态move算法属于雷同汇合的放于同一个列表中，其余的放于另一个列表中。
f.将KK中原来要划分的汇合删除，退出划分后的两个汇合。循环执行上述步骤，晓得KK中汇合个数和标记位llag值雷同或者KK中汇合个数等于K中状态个数，则退出循环。
4、输入
输入同样为DFA的定义模式，先输入M=(K,E,f,S,Z)，再输入其中的f。
五、试验小结
本次试验次要遇到了以下问题：
1、输出存储问题
输出要求应用定义模式，须要辨别输出的元素，别离失去状态集，输出符号集，初态集以及终态集。通过python中的split函数将输出的字符串别离以’{‘和’}’离开，再通过循环操作取出失去的二维列表中每一个元素的第二个元素，即为所求的状态集，输出符号集，初态集以及终态集，再输入f的具体弧。
2、子集划分算法问题
子集划分算法须要对划分后失去的汇合始终执行划分算法，然而会有一个示意划分结束的后果，在程序中通过设立两个条件来判断是否划分结束，一是划分失去的子集个数是否等于状态集中状态个数，若是则阐明每个状态都为一个子集，即必定划分完结。另一判断条件为设置一个标记位，通过观察标记位的数值来判断本次划分算法是否执行，若没有执行则阐明曾经划分结束，同样退出循环。
3、输入问题
输入的模式为DFA的定义模式，通过对格局的管制，将本来定义中的列表类型都转为汇合类型，最初输入。同时定义中的f须要独自输入。
六、附件
1、源代码
K = [] # 状态E = [] # 符号f = [] # 弧f1 = [] # 新弧S = [] # 初态Z = [] # 终态zanshi1 = [] # 寄存五元组模式1KK = [] # 最终状态集#M=({1,2,3,4,5,6,7},{a,b},f,{1},{5,6,7})# 输出def putin(): print('输出DFA M') M = input('以定义模式输出DFA(如:M=(K,E,f,S,Z):)') N = M.split('}') for i in N: zanshi1.append(i.split('{')) K1 = (zanshi1[0][1]) K1 =K1.split(',') for i in K1: K.append(i) E1 = (zanshi1[1][1]) E1 =E1.split(',') for i in E1: E.append(i) S1 = (zanshi1[2][1]) S1 =S1.split(',') for i in S1: S.append(i) Z1 = (zanshi1[3][1]) Z1 =Z1.split(',') for i in Z1: Z.append(i) print('输出f中弧的条数:') n = int(input()) print('输出弧(别离输出状态1,输出符号,状态2,以空格辨别换行完结,示意为$)') for i in range(n): f.append([]) a = input() f[len(f)-1] = a.split(' ')def move(a, e, f): # a为列表 e为一个符号 s = [] for i in a: for j in range(len(f)): if i == f[j][0] and f[j][1] == e: s.append(f[j][2]) return sorted(s)# 子集划分算法def operation(): a = [] for x in K: if x not in Z: a.append(x) KK.append(a) KK.append(Z) while len(KK) != len(K): llag = 0 for i in range(len(KK)): ziji = KK[i] glag = 0 for jj in range(len(E)): ziji1 = move(ziji, E[jj], f) flag = 0 for k in range(len(KK)): if len(set(ziji1).difference(set(KK[k]))) != 0: flag = flag+1 if flag == len(KK): glag = glag + 1 break if glag == 1: ilag = jj zhenziji1 = [] zhenziji1.append(ziji[0]) ziji1 = move(zhenziji1, E[ilag], f) for k in range(len(KK)): if len(set(ziji1).difference(set(KK[k]))) == 0: hlag = k break zhenziji2 = [] for j in range(1, len(ziji)): zz = [] zz.append(ziji[j]) ziji1 = move(zz, E[ilag], f) if len(set(ziji1).difference(set(KK[hlag]))) == 0: zhenziji1.append(ziji[j]) else: zhenziji2.append(ziji[j]) KK.pop(i) KK.append(zhenziji1) KK.append(zhenziji2) else: llag = llag+1 if llag == len(KK): break# 运行putin()operation()for yy in KK: if len(yy) >= 2: for i in range(1, len(yy)): if yy[i] in K: K.remove(yy[i]) if yy[i] in S: S.remove(yy[i]) if yy[i] in Z: Z.remove(yy[i]) for yyy in f: if yyy[0] == yy[i]: yyy[0] = yy[0] if yyy[2] == yy[i]: yyy[2] = yy[0]for yy in f: if yy not in f1: f1.append(yy)for i in range(len(K)): K[i] = int(K[i])for i in range(len(S)): S[i] = int(S[i])for i in range(len(Z)): Z[i] = int(Z[i])print('输入最小化DFA M')print('M1=(',set(K),',',set(E), ',', 'f', ',',set(S), ',', set(Z), ')')print('其中f为')k = 0for yy in f1: print('f(',yy[0],',',yy[1],')=',yy[2],end=' ') k = k+1 if k == 4: print('\n') k = 02、运行后果截图