资源描述：
《编译原理课程设计--nfa转化为dfa的转换算法及实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理课程实践报告设计名称：NFA转化为DFA的转换算法及实现二级学院：数学与计算机科学学院专业：计算机科学与技术班级：计科本091班姓名：林玉兰学号：0904402102指导老师：梁德塞日期：2012年6月摘要确定有限自动机确定的含义是在某种状态，面临一个特定的符号只有一个转换，进入唯一的一个状态。不确定的有限自动机则相反，在某种状态下，面临一个特定的符号是存在不止一个转换，即是可以允许进入一个状态集合。在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的
2、反复，无疑会影响到FA的工作效率。而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。对于任意的一个不确定有限自动机（NFA）都会存在一个等价的确定的有限自动机（DFA），即L(N)=L(M)。本文主要是介绍如何将NFA转换为与之等价的简化的DFA，通过具体实例，结合图形，详细说明转换的算法原理。关键词：有限自动机；确定有限自动机（DFA），不确定有限自动机（NFA）AbstractFiniteautomataisdeterminateandindeterminatetwoclass.Determinethemeani
3、ngisinacertainstate,facesaparticularsymbolonlyoneconversion,enteronlyonestate.Notdeterministicfiniteautomataistheopposite,inacertainstate,facesaparticularsymbolisthepresenceofmorethanoneconversion,thatistobeallowedtoenterastateset.NondeterministicfinitestateautomataNFA,becauseofsomestat
4、earetransferredfromanumberofpossiblefollow-upstatearechosen,soaNFAsymbolstringrecognitionmustbeatrialprocess.Thisuncertaintytotherecognitionprocessbroughtaboutbyrepeated,willundoubtedlyaffecttheefficiencyoftheFA.WhiletheDFAisdetermined,convertingNFAtoDFAwillgreatlyimprovetheworkingeffic
5、iency,thusconvertingNFAtoDFAisitsnecessary.Foranyanondeterministicfiniteautomaton(NFA)canbeanequivalentdeterministicfiniteautomaton(DFA),L(N)=L(M).ThispapermainlyintroduceshowtoconvertNFAtoequivalentsimplifiedDFA,throughconcreteexamples,combinedwithgraphics,adetaileddescriptionofthealgo
6、rithmprincipleofconversion.Keywords:：finiteautomata;deterministicfiniteautomaton(DFA),nondeterministicfiniteautomaton(NFA目录1.前言：11.1背景11.2实践目的11.2课程实践的意义12.NFA和DFA的概念22.1不确定有限自动机NFA22.2确定有限自动机DFA33．从NDF到DFA的等价变化步骤53.1转换思路53.2.消除空转移53.3子集构造法74程序实现94.1程序框架图94.2数据流程图94.3实现代码104.4运行环境104.5程
7、序实现结果105.用户手册126.课程总结：127.参考文献128.附录131.前言：1.1背景有限自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有限自动机（FiniteAutomate）是用来模拟实物系统的数学模型，它包括如下五个部分：·有穷状态集States·输入字符集Inputsymbols·转移函数Transitions·起始状态Startstate·接受状态Acceptingstate(s)1.2实践目的（1）设计、编制
