编译原理实验DFA最小化.docx

确定有穷自动机的最小化
目录
一、实验名称 2
二、实验目的 2
三、实验原理 2
1、DFA的定义 2
2、无用状态 2
3、状态等价条件 2
四、实验思路 3
1、输入 3
2、move算法 3
3、子集划分算法 3
4、输出 4
五、实验小结 4
1、输入存储问题 4
2、子集划分算法问题 4
3、输出问题 4
六、附件 4
1、源代码 4
2、运行结果截图 7
一、实验名称
确定有穷自动机的最小化
二、实验目的
1、输入DFA,输出等价的状态数最少的DFA;
2、实现子集划分算法;
3、输入和输出均以定义的形式。
三、实验原理
1、DFA的定义
一个确定的有穷自动机M是一个五元组,M=(K,E,f,S,Z)其中
K是一个有穷集,它的每个元素称为一个状态;
E是一个有穷字母表,它的每个元素称为一个输入符号;
f是转换函数,是K×E->K上的映像,即,如f(ki,a)=kj(ki∈K,kj∈K)就意味着,当前状态为ki,输入字符为a时,将转换到下一状态kj,我们把kj称作ki的一个后继状态;
S∈K,是唯一的一个初态;
Z包含于K,是一个终态集,终态也称可接受状态或结束状态。
2、无用状态
所谓有穷自动机的无用状态,是指这样的状态:从该自动机的开始状态出发,任何串也不能到达的那个状态。或者从这个状态没有通路到达状态。
3、状态等价条件
——状态s和t必须同时为可接受状态或不可接受状态
——对于所有输入符号,状态s和状态t必须转换到等价的状态里。
四、实验思路
本次实验采用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的下一个状态,将这些状态放于新列表中。
3、子集划分算法
定义operation()函数为子集划分算法函数,具体执行步骤如下:
:终态集和非终态集,存于KK中,KK存放最终划分后得到的集合。
,子集划分算法划分最细的情况是每个状态都为一个子集,所以以此作为循环条件。若KK中集合个数不等于K中状态个数,则继续循环。
=0用来决定是否跳出循环,每不执行一次划分算法则llag加1,若最终llag等于KK长度,说明此次循环没有子集划分,则说明划分完毕,退出循环。
,判断他们进过move算法得到的集合是否是KK中已有的集合,若是则不执行划分,否则执行划分算法。
e. 若执行划分算法,则先算出集合中首个状态的move算法得到的集合属于哪个已知集合,再对其他状态进行同样操作,和首个状态