《编译原理课程设计--NFA转化为DFA的转换算法及实现》由会员分享，可在线阅读，更多相关《编译原理课程设计--NFA转化为DFA的转换算法及实现（26页珍藏版）》请在金锄头文库上搜索。
1、编译原理课程实践报告设计名称：NFA专化为DFA勺转换算法及实现二级学院：数学与计算机科学学院专业：计算机科学与技术班级：计科本091班姓名：林玉兰学号:0904402102指导老师：梁德塞日期：2012 年6月摘要确定有限自动机确定的含义是在某种状态， 面临一个特定的符号只有一个转换，进入唯一的一个状态。不确定的有限自动机则相反，在某种状态下，面临一 个特定的符号是存在不止一个转换，即是可以允许进入一个状态集合。在非确定的有限自动机NFA中，由于某些状态的转移需从若干个可能的后续 状态中进行选择，故一个NFA对符号用的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到
2、FA的工作效率。而DFA则是确定的，将NFA专化为DFAt大大提高工作效率,因此将NFA专化为DFA1有其一定必 要的。对于任意的一个不确定有限自动机（NFA都会存在一个等价的确定的有限 自动机（DFA,即L（N）=L（M）。本文主要是介绍如何将NFA转换为与之等价的简 化的DFA通过具体实例，结合图形，详细说明转换的算法原理。关键词： 有限自动机；确定有限自动机（DFA） ，不确定有限自动机（NFA）AbstractFinite automata is determinate and indeterminate two class. Determine the meaning is in a
3、 certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces a particular symbol is the presence of more than one conversion, that is to be allowed to enter a state set.Non deterministic finite state
4、 automata NFA, because of some state are transferred from a number of possible follow-up state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency of the FA. While the DF
5、A is determined, converting NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary.For any a nondeterministic finite automaton ( NFA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M ). This paper mainly introduces how to conve
6、rt NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detailed description of the algorithm principle of conversion.Keywords: ： finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA目录11111. 前言 ： 1.1 背景 1.2 实践目的 1.3 课程实践的意
7、义2 .NFA和DFA的概念 22.1 不确定有限自动机NFA 22.2 确定有限自动机DFA 33 .从NDF!J DFA勺等价变化步骤 53.1 转换思路 53.2 . 消除空转移 53.3 子集构造法 74 程序实现 94.1 程序框架图 94.2 数据流程图 94.3 实现代码 104.4 运行环境 104.5 程序实现结果 105 . 用户手册 126 . 课程总结 ： 127 .参 考文 献 128 . 附录 131.前言：A A1.1 背景有限自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合， 引入有穷自动机这个理论， 正是为词法分析程
8、序的自动构造寻找特殊的方法和工具。有限自动机( Finite Automate )是用来模拟实物系统的数学模型，它包括如下五个部分：?有穷状态集States?输入字符集Inputsymbols?转移函数Transitions? 起始状态Start state? 接受状态Accepting state(s)1.2 实践目的(1)设计、编制、调式一个有穷自动机程序，加深对NFA转换为DFA的原理的理解。(2)掌握NFA确定化的过程。1.2 课程实践的意义通过本课程设计教学所可以使我们充分理解和掌握NFA DFA以及NFA确定化过程的相关概念和知识， 理解和掌握子集法的相关知识和应用， 编程实现对输
9、 入NFA转换成DFA输出的功能。2.NFA 和 DFA 的概念2.1 不确定有限自动机NFANFA(nondeterministic finite-state automata) 即非确定有限自动机,个非确定的有限自动机NFA M是一个五元式：NFA M =(S, 2 U , 6 , S0, F)其中S一有限状态集，2U e 输入符号加上e，即自动机的每个结点所 射出的弧可以是2中一个字符或是e.S0 初态集F终态集6 转换函数 S X 2 U -2S(2S -S的幂集 S 的子集构成的集合)例 1 ： NFA M=(S,P,Z,0,1,f,s,p,z)其中f(s,0)=pf(z,0)=pf
10、(p,1)=zf(z,1)=pf(s,1)=s,z NFA 的状态图表示如下：第 # 页，共 22 页NFA矩阵表示:状态与01SPS,Z0PZ0ZPP12.2确定有限自动机DFADFA(deterministic finite-state automata)即确定有限自动机，一个确定 的有限自动机DFA M是一个五元式：M=(S,2 , 6 , S0, Z)其中：S 一有限状态集2 一输入字母表6 一映射函数(也称状态转换函数)S x、一 S6 (s,a)=S, S, S S, a 2S0 初始状态 S0 C SZ一终止状态集Z S其中f的定义为:例 2: DFA M=(S,U,V,Q,a,
11、b,f,s,Q)f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=Vf(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=QDFA的状态图表示：假如DFAM含有m个状态，n个输入符，那么这个状态含有 m个节点，每个 节点最多有n个弧射出，整个图整个图含有唯一一个初态结点和若干个终态结 点，初态结点冠以双箭头“=”或标以“-，终态结点用双圈表示或标以“ +”, 若f(ki ,a)=kj ,则从状态结点ki到状结点kj画标记为a的弧：DFA矩阵表示：一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k
12、行a列为f(k,a)的值。用双箭头=标明初态；否则第一行即是初态，相应终态行在表的右端标以1,非终态标以0.状态宅符abSUV0UQV0VUQ0QQQ13.从NDF到DFA的等价变化步骤事实已经证明了不管是非确定的有限自动机 M还是具有e-转移的非确定的 有限自动机，都可以找到一个与之等价的确定有限自动机，使得L (M =L (MT)3.1 转换思路由非确定的有限自动机出发构造与之等价的确定的有限自动机的办法是确定的有限自动机的状态对应于非确定的有限自动机的状态集合，即要使转换后的DFA的每一个X态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入 一个输入符号后可能到达的所有状态，
13、也就是说，在读入符号用a1a2a3- an之后，该DFA处在这样一个状态，该状态表示这个 NFA的状态的一个子集T,而T 是从NFA的开始状态沿着某个标记为a1a2a3 - an的路径可以到达的那些状态。3.2 .消除空转移.消除N形式的产生式，即消除空转移。状态集合I的a弧转换Ia:定义为一状态集，是指从状态集I出发先经过a弧后再经过若干条e弧而能到达的状态的集合。可以写作：Ia= e-closure(J) , J=move(I,a),其中，J是从I中任 一状态出发经过一条a弧到达的状态集合，记为move(I,a)。s表示NFA的状态，T表示NFA的状态集合，a表示一个input symbo
14、l -transition（ 转换）就是说 input symbol 为 e 时的 transition（ 转换）作(operation)描述(description)closure(s)从NFA勺状态s出发，只通过e -transition 到达的NFA的 伏态集合-closure(T)NFA勺集合T中的状态p,只通过e -transition 到达的NF 的状态集合，再求这些集合的交集。用数学表达就是p|p属于8-closure（t） , t 属于 Tove(T,a)NFA勺集合，这个集合在input symbol为a,状态为T中任 意状态情况下，通过一个转换得到的集合例如:对于以下状态图中：e -closure(0)=0,1,2,4,7在这里设 I=0,1,2,4,7,则因为有 move(I,a)=3,8=J,所以Ia= -closure(J)=e -closure(3,8)=1,2,3,4,6,7,83.3 子集构造法，具体转换，采用子集构确定化每个多重转移，即拆分多值函数为单位函数造法。以下面的基于字母表、=a,b上的具有e -转移的非确定有限自动机 M为例。步骤1:以I, Ia、Ib等为列做表，其中I列第一行的内容是初态的e -闭包所 得到的状态集合。并以此为I计算Ia、I
