编译原理实验DFA最小化

1、2016.11.09确定有穷自动机的最小化目录一、实验名称2二、实验目的2三、实验原理21、DFA的定义22、无用状态23、状态等价条件2四、实验思路31、输入32、move算法33、子集划分算法34、输出4五、实验小结41、输入存储问题42、子集划分算法问题43、输出问题4六、附件41、源代码42、运行结果截图7一、实验名称确定有穷自动机的最小化二、实验目的1、输入DFA，输出等价的状态数最少的DFA；2、实现子集划分算法；3、输入和输出均以定义的形式。三、实验原理1、DFA的定义一个确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中a. K是一个有穷集，它的每个元素称为一个状态

2、；b. E是一个有穷字母表，它的每个元素称为一个输入符号；c. f是转换函数，是KE-K上的映像，即，如f(ki,a)=kj(kiK,kjK)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；d. SK，是唯一的一个初态；e. Z包含于K，是一个终态集，终态也称可接受状态或结束状态。2、无用状态所谓有穷自动机的无用状态，是指这样的状态：从该自动机的开始状态出发，任何串也不能到达的那个状态。或者从这个状态没有通路到达状态。3、状态等价条件a.一致性条件状态s和t必须同时为可接受状态或不可接受状态b.蔓延性条件对于所有输入符号，状态s和状态t必须转换

3、到等价的状态里。四、实验思路本次实验采用python完成。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的下一个状态，将这些状态放于新列表

4、中。3、子集划分算法定义operation()函数为子集划分算法函数，具体执行步骤如下：a.将K中的状态集分为两种：终态集和非终态集，存于KK中，KK存放最终划分后得到的集合。b.设立循环条件，子集划分算法划分最细的情况是每个状态都为一个子集，所以以此作为循环条件。若KK中集合个数不等于K中状态个数，则继续循环。c.设立标志位llag=0用来决定是否跳出循环，每不执行一次划分算法则llag加1，若最终llag等于KK长度，说明此次循环没有子集划分，则说明划分完毕，退出循环。d.对KK中的集合依次进行操作，判断他们进过move算法得到的集合是否是KK中已有的集合，若是则不执行划分，否则执行划分算

5、法。e. 若执行划分算法，则先算出集合中首个状态的move算法得到的集合属于哪个已知集合，再对其他状态进行同样操作，和首个状态move算法属于相同集合的放于同一个列表中，其他的放于另一个列表中。f.将KK中原来要划分的集合删除，加入划分后的两个集合。循环执行上述步骤，知道KK中集合个数和标志位llag值相同或者KK中集合个数等于K中状态个数，则退出循环。4、输出输出同样为DFA的定义形式，先输出M=(K,E,f,S,Z)，再输出其中的f。五、实验小结本次实验主要遇到了以下问题：1、输入存储问题输入要求使用定义形式，需要区分输入的元素，分别得到状态集，输入符号集，初态集以及终态集。通过pytho

6、n中的split函数将输入的字符串分别以和分开，再通过循环操作取出得到的二维列表中每一个元素的第二个元素，即为所求的状态集，输入符号集，初态集以及终态集，再输出f的具体弧。2、子集划分算法问题子集划分算法需要对划分后得到的集合一直执行划分算法，但是会有一个表示划分完毕的结果，在程序中通过设立两个条件来判断是否划分完毕，一是划分得到的子集个数是否等于状态集中状态个数，若是则说明每个状态都为一个子集，即肯定划分结束。另一判断条件为设置一个标志位，通过观察标志位的数值来判断本次划分算法是否执行，若没有执行则说明已经划分完毕，同样退出循环。3、输出问题输出的形式为DFA的定义形式，通过对格式的控制，将

7、原本定义中的列表类型都转为集合类型，最后输出。同时定义中的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(E21414020 陈国柱) print(输入DFA M) M = input(以定义形式输入DFA(如:M=(K,E,f,S,Z):) N = M.split() for i in N: zanshi1.append(i.split()

8、 K1 = (zanshi101) K1 =K1.split(,) for i in K1: K.append(i) E1 = (zanshi111) E1 =E1.split(,) for i in E1: E.append(i) S1 = (zanshi121) S1 =S1.split(,) for i in S1: S.append(i) Z1 = (zanshi131) Z1 =Z1.split(,) for i in Z1: Z.append(i) print(输入f中弧的条数:) n = int(input() print(输入弧(分别输入状态1,输入符号,状态2,以空格区分换行

9、结束,表示为$) for i in range(n): f.append() a = input() flen(f)-1 = a.split( )def move(a, e, f): # a为列表 e为一个符号 s = for i in a: for j in range(len(f): if i = fj0 and fj1 = e: s.append(fj2) 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 l

10、en(KK) != len(K): llag = 0 for i in range(len(KK): ziji = KKi glag = 0 for jj in range(len(E): ziji1 = move(ziji, Ejj, f) flag = 0 for k in range(len(KK): if len(set(ziji1).difference(set(KKk) != 0: flag = flag+1 if flag = len(KK): glag = glag + 1 break if glag = 1: ilag = jj zhenziji1 = zhenziji1.a

11、ppend(ziji0) ziji1 = move(zhenziji1, Eilag, f) for k in range(len(KK): if len(set(ziji1).difference(set(KKk) = 0: hlag = k break zhenziji2 = for j in range(1, len(ziji): zz = zz.append(zijij) ziji1 = move(zz, Eilag, f) if len(set(ziji1).difference(set(KKhlag) = 0: zhenziji1.append(zijij) else: zhenz

12、iji2.append(zijij) 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 yyi in K: K.remove(yyi) if yyi in S: S.remove(yyi) if yyi in Z: Z.remove(yyi) for yyy in f: if yyy0 = yyi: yyy0 = yy0 if yyy2 = yyi: yyy2 = yy0for yy in f: if yy not in f1: f1.append(yy)for i in range(len(K): Ki = int(Ki)for i in range(len(S): Si = int(Si)for i in