你们暗黑3有没有经常自动dfa最小化化的现象

来源：蜘蛛抓取(WebSpider) 时间：2018-11-10 00:56 标签： dfa最小化

确定有穷自动机的dfa最小化化1 目录 ┅、实验名称 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、运行结果截图 .72 一、实验名称 确定有穷自动机的dfa最小化化 二、实验目的 1、输入 DFA输出等价的状态数最少的 DFA； 2、实现子集划分算法； 3、输入和输出均以定义的形式。 三、实验原理 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 必须转换到等价的状 态里。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 的下一个状 态，将这些状态放于新列表中 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 中原来要划分的集合删除，加入划分后的两个集合循环执行上述4 步骤，知道 KK 中集合个数和标志位 llag 值相同或者 KK 中集合个数等于 K 中状 态個数则退出循环。 4、输出 输出同样为 DFA 的定义形式先输出 M=(K,E,f,S,Z)，再输出其中的 f 五、实验小结 本次实验主要遇到了以下问题： 1、输入存储问題 输入要求使用定义形式，需要区分输入的元素

我要回帖

更多关于 dfa最小化 的文章

 

随机推荐