编译原理课程设计：NFA的确定化

《编译原理课程设计：NFA的确定化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机系编译原理课程设计课程名称:编译原理课程代码:436105题目:NFA的确定化年级/专业/班:学生姓名:学号:指导老师:开题时间:完成时间:-27-目录一、引言-4-二、设计目的与任务-4-1、设计目的：-4-2、设计任务：-4-三、设计方案-5-1、总体设计-5-2、详细设计-11-3、程序清单-14-4、程序调试与体会-23-5、运行结果-24-四、结论-26-五、致谢-26-六、参考文献-26-2设计进度完成情况-27--27-摘要确定有限自动机确定的含义是在某种状态，面临一个特定的符

2、号只有一个换，进入唯一的一个状态。不确定的有限自动机则相反．在某种状态下，面临个特定的符号是存在不止一个转换即是可以允许进入一个状态集合。在非确定的有限自动机NFA中．由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到NFA的工作效率。而DFA则是确定的，将NFA转化为DFA将大大提高工作效率，因此将NFA转化为DFA是必要的。对任意的一个不确定有限自动机（NFA），都会存在一个等价的确定的有限自动

3、机（DFA），即L（N）=L(M)。本文主要是介绍如何将NFA转换为与之等价的简化DFA，通过具体实例，结合图形，详细说明转换的算法原理。关键词：有限自动机；确定有限自动机（DFA），不确定有限自动机（NFA）-27-AbstractFiniteautomataaredeterminateandindeterminatetwoclasses.Determinethemeaningisinacertainstate,facesaparticularsymbolonlyoneconversion,en

4、teronlyonestate.Notdeterministicfiniteautomataaretheopposite.Inacertainstate,Facesasymbolisthepresenceofmorethanoneconversion,whichistobeallowedtoenterastateset.NondeterministicfinitestateautomataNFA,becauseofsomestatearetransferredfromanumberofpossib

5、lefollow-upstatesarechosen,soNFAsymbolstringrecognitionmustbeatrialprocess.Thisuncertaintytotherecognitionprocessbroughtaboutbyrepeated.WillundoubtedlyaffecttheefficiencyoftheNFA.WhiletheDFAisdetermined,conveningNFAtoDFAwillgreatlyimprovetheworkingeff

6、iciency,thusconvertingNFAtoDFAisitsnecessary.Foranyanondeterministicfiniteautomaton(NFA)canbeanequivalentdeterministicfiniteautomaton(DFA),L(N)=L(M).ThispapermainlyintroduceshowtoconvertNFAtoequivalentsimplifiedDFA,throughconcreteexamples,combinedwith

7、graphics,adetaileddescriptionofthealgorithmprincipleofconversion.Keywords:finiteautomata;deterministicfiniteautomaton(DFA),nondeterministicfiniteautomaton(NFA).-27-《编译原理》课程设计--NFA的确定化设计一、引言在编译系统中,词法分析阶段是整个编译系统的基础。对于单词的识别，有限自动机FA是一种十分有效的工具。有限自动机由其映射f是否

8、为单值而分为确定的有限自动机DFA和非确定的有限自动机NFA。在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。而DFA引擎在任意时刻必定处于某个确定的状态，它搜索是无需象NFA一样必须记录所有的可能路径（tracemultiplepossibleroutesthroughtheNFA），这也是DFA运行效率高于DFA的原因。而已经证明D