欢迎来到天天文库
浏览记录
ID:13385830
大小:211.50 KB
页数:10页
时间:2018-07-22
《朱航宇-20112878-编译原理合设计》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、编译原理合设计指导教师:李宏芒专业班级:信安11-1姓名:朱航宇学号:2011287810-10-一.课程设计目的《编译原理》是计算机专业的一门重要的专业课程,其中包含大量软件设计思想。大家通过课程设计,实现一些重要的算法,或设计一个完整的编译程序模型,能够进一步加深理解和掌握所学知识,对提高自己的软件设计水平具有十分重要的意义。二.课程设计内容(12,13题:12题DFA状态最少化的程序实现和13题把NFA确定化为DFA的算法实现,合并为一题,将NFA确定化为DFA,再将DFA化简即最小化。)我在选择课程设计题目时,只选择了12题
2、DFA的最小化。但由于12题工作量较小同时为了提高我的编程能力我将13题NFA确定化为DFA,将这两题合并为一题,即NFA确定化到最小化的实现。NFA的确定化和DFA的最小化主要是为了更好地使用状态转换图构造词法分析程序和词法分析程序的自动生成。设计并实现将NFA确定化为DFA的子集构造算法以及DFA的最小化,从而更好地理解有限自动机之间的等价性,掌握词法分析器自动产生器的构造技术。三.设计要求构造一程序,实现:将给定的NFAM(其状态转换矩阵及初态、终态信息从键盘输入),确定化为DFAM’。(要先实现ε-CLOSURE函数和Ia函
3、数)。输出DFAM’(其状态转换矩阵及初态、终态信息输出到屏幕上)。然后将由确定化后的的DFAM的有限状态集S划分成若干互不相交的子集,使得:任何不同的两个子集中的状态都是可区别的,而同一子集中的任何两个状态都是等价的(要利用Ia函数,但并不需要构造ε-CLOSURE函数,因这是DFA)。输出化简后的DFAM’(其状态转换矩阵及初态、终态信息输出到屏幕上)。四.设计思路4.1NFA确定化为DFA 1.非确定有限自动机NFA一个非确定有限自动机(NFA)M是一个五元式M=(S,∑,δ,S0,F)其中(1)S是一个有限集,它的每一个元
4、素称为一个状态;(2)∑是一个有穷字母表,它的每一个元素称为一个输入字符;(3)δ是一个从S×∑*到S的子集映照;(4)S0属于∑,是一个非空初态集;(5)F属于S,是一个终态集(可空)。显然,一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图:该图含有m个状态结点,每个节点可射出若干条箭弧与别的结点相连接,每条弧用∑*中的一个字(不一定要相同而且可以是空字)做标记(称为输入字),整张图至少含有一个初态10-10-结点以及若干个(可以是0个)终态结点。对于∑*中的任何一个字a,若存在一条从某一初态结点到某一终态结点的通路
5、,且这条通路上所有弧的标记字依序连接城的字(忽略那些标记为空字ε的弧)等于啊,则称a可为NFAM所识别。若M的某些结点既是初态结点又是终态结点,后者存在一条弧从某个出台节点到某个终态结点的ε通路,则空字ε可为M所接受。2.确定有限自动机DFA的最小化一个确定有限自动机(NFA)M是一个五元式M=(S,∑,δ,s0,F)其中(1)S是一个有限集,它的每一个元素称为一个状态;(2)∑是一个有穷字母表,它的每一个元素称为一个输入字符;(3)δ是一个从S×∑到S的单值部分映射。δ(s,a)意味着:当现行状态为s、输入字符为a时,将转入下一个
6、状态s’,s’是s的后继状态;(4)s0∈S,是唯一的初态;(5)F属于S,是一个终态集(可空)。显然,一个DFA可用一个状态转换矩阵表示,该矩阵的行表示状态,列表时输入字符,矩阵元素表示δ(s,a)的值。一个DFA也可以表示成一张状态转换图,假设DFAM含有m个状态和n个输入字符,那么,该图含有m个状态结点,每个节点最多有n条箭弧与别的结点相连接,每条弧用∑中的一个字做标记,整张图含有唯一的一个初态结点和若干个(可以是0个)终态结点。对于∑中的任何一个字a,若存在一条从某一初态结点到某一终态结点的通路,且这条通路上所有弧的标记字依
7、序连接城的字等于啊,则称a可为DFAM所识别。若M的某些结点既是初态结点又是终态结点,后者存在一条弧从某个出台节点到某个终态结点的ε通路,则空字ε可为M所接受。DFAM所能识别的字的全体记为L(M)。3.NFA与DFA的联系在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择,故一个NFA对符号串的识别必然是一个试探的过程。这种不确定性识别过程带来的反复,无疑会影响到FA的工作效率。而DFA则是确定的,将NFA转化为DFA大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。程序中采用子集法来实现
8、NFA确定化为DFA。4.2DFA的最小化一个有限自动机M的化简是指:寻找一个状态数比M少的DFAM’,使得L(M)=L(M’).假定s和t是M的两个不同状态,如果分别从状态s和t出发能读出同样的某个字w而停于终态,则称s和t是等价的
此文档下载收益归作者所有