资源描述：
《编译原理实验NFA确定化为DFA》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2016.11.02不确定有穷状态自动机的确定化8目录一、实验名称2二、实验目的2三、实验原理21、NFA定义22、DFA的定义23、closure函数24、move函数3四、实验思路31、输入32、closure算法33、move算法34、构造子集45、输出4五、实验小结41、输入存储问题42、closure算法问题43、输出问题5六、附件51、源代码52、运行结果截图78一、实验名称不确定有穷状态自动机的确定化二、实验目的输入：非确定有穷状态自动机NFA输出：确定化的有穷状态自动机DFA三、实验原理1、NFA定义一个不确定的有穷自动机M是一个五
2、元组，M=(K,E,f,S,Z)其中a.K是一个有穷集，它的每个元素称为一个状态；b.E是一个有穷字母表，它的每个元素称为一个输入符号；c.f是一个从K×E*到K的子集的映像，即：K*E*->2k，其中2k表示K的幂集；d.S包含于K，是一个非空初态集；e.Z包含于K，是一个终态集。2、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
3、)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；d.S∈K，是唯一的一个初态；e.Z包含于K，是一个终态集，终态也称可接受状态或结束状态。3、closure函数8状态集合I的ε—闭包，表示为ε—closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。4、move函数状态集合I的a弧转换，表示为move(I,a)，定义为状态集合J，其中J是所有那些从I中的某一状态经过一条a弧而到达的状态的全体。四、实验思路本次实验采用python完成。1、输入根据课本NFA的
4、定义，输入五元组，依次输入状态集、输入符号、初态集、终态集以及映像，将这些分别存入五个列表中。其中关于映像的输入格式：先输入状态一，再输入输入符号，最后输入状态二，一次输入一条弧。2、closure算法定义closure函数形式为closure(a,f)，其中，a为要做closure闭包的状态集合，f为NFA的映像的集合。具体思想为：a.设立一个最终返回结果的列表b，初值与列表a相等。设立一个空列表s，用于存放每次closure闭包新加入的状态。b.执行while循环，此循环判断条件为1，即会一直执行下去，直到遇到closure闭包没有新增状态的时
5、候执行结束。c.对a中的每一个状态求closure闭包，即判断f中状态一等于a中状态的弧，再判断f中该状态的弧是否为ε（具体代码中用’$’代替），若是，则将该弧的状态二加入s中。d.判断s是否为空，若为空则说明此次循环没有新增状态，即说明closure闭包在上一次循环时已执行完毕，输出上次循环的结果b。若s不为空，说明本次循环仍然有新增状态，则将新增状态加入b中，并且将新增的状态集合赋值给a，以新增的状态集继续做循环判断，直到某次循环s为空结束。3、move算法8move算法的核心思想与closure算法一致，其函数形式为move(a,e,f)，其
6、中e为move算法move(I,a)的a。move算法只需要求从状态集合中某一状态经过一条a弧而到达的状态全体，所以不需要进行while循环执行多次，只需执行closure算法中c步骤一次即可。4、构造子集建立两个列表C1、C2，其中C1用于存放最终的状态集，C2作为标记使用，对应C1中的子集，若C1中的子集也进行了closure闭包则C2中相应元素标记为1，否则为0。具体思想为：a.首先对初态集进行closure闭包，存于C1中，C2的第一个元素赋值为0。b.标记C2第一个元素为1，对C1中第一个集合先做move算法再做closure算法，若其中
7、一个算法得出空集合则直接返回空列表，否则判断C1中是否有该状态集，若无则加入C1中，C2中相应元素赋值为0，表示未标记。c.重复执行b步骤，直到C2中所有元素为1，表示标记完毕，执行完成，所得到C1为最终状态子集。5、输出采用矩阵形式输出，C1中每个状态集合的下标为最终合并后的状态。五、实验小结本次实验主要遇到了以下问题：1、输入存储问题若根据课本形式应输入M=(K,E,f,S,Z)，再对f进行展开，虽然用算法实现这一形式不难，但是对于后续的操作不太方便，所以最终选择了依次输出五元组，分别存于五个列表中。2、closure算法问题最初想用递归的思想
8、实现closure算法，即每次进行一步closure闭包，返回结果为新得到的状态集的closure闭包，但是对于递归结束的
