dfa最小化算法的探讨与改进

《dfa最小化算法的探讨与改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、DFA最小化算法的探讨与改进摘要我在别的教材中看到DFA最小化算法是“分割法”，但是我觉得算法存在一定的问题，所以我将在下文中分析该算法的漏洞所在，并提出了改进的算法。1引言开始没有学习编译原理之前，我原以为它是一门以编程为主的科目，主要是进行低级语言的编写，编译原理是一种翻译的程序，它是现代计算机系统的基本组成部分。我们学习了DFA最小化算法，但是存在一些问题，下面我们要进行探讨和一些我自己的看法。2DFA及DFA的化简编译程序一般包括词法分析、语法分析、语义分析、中间代码生成、目标代码生成、代码优化、表格管理和

2、出错处理等成分。词法分析是编译程序要做的首要工作，它接收输入的源程序符号串，按照构词规则分割为一个个的单词符号并输出。有穷自动机是一种能进行运算和自我控制的装置，能准确识别单词符号。因此，可以通过构造有穷自动机来实现词法分析程序的自动构造。有穷自动机分为确定的有穷自动机DFA和不确定的有穷自动机NFA两种。定义1DFA—个确定的有穷自动机M是一个五元组，M=（K，2，f，S，Z），其中：K是一个存穷集，其元素称为状态；2是一个右穷字母表，其元素称为输入符号；SEK,称为初态；ZCK，是终态集；f是转换函数，是KX上

3、的映射，f（ki，a）=kj，（kieK，幻£1＜）表示状态1^，输入符为a时，转换为状态kj。定义2无用状态从自动机的开始状态出发，任何输入串也不能到达的那个状态;或者从这个状态没有通路到达终态的状态。定义3等价状态如果说两个状态s和t是等价的，应满足如下条件：（a）—致性条件：s和t必须同时为终态或为非终态；（b）蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。一个DFAM可以通过消除无用状态和合并等价状态而转化为一个最小化的与之等价的DFAM’。该过程称为DFA的化简。3“分割法”化简DFA对

4、一个DFAM最少化的基本思想是：把M的状态集划分为一些不相交的子集，使得任何两个不同子集中的状态是（可区别）不等价的，而同一子集的任何两个状态是等价的。具体算法过程描述如卞：(1)把s划分为终态和非终态两个子集，形成初始划分n;⑺假定n己含m个子集，记为n={Il，I2,，Im}，则对每一个Ii和毎一个aE2考察：Iia=f(Ii，a)，如Iia中的状态分别落于n中P个不同的子集，则子集Ii将被P个更小的状态子集Iil，Ii2,Ojip所细分。令细分后所得的状态集合为nnew;(3)重复步骤(2)直到直至所含的子集

5、数不再增加为止，Knew=n；(4)对n中的每个子集ii，若该子集包含原有的初态，则此代表状态便力最小化后M的初态；该子集包含原右的终态，则此状态便为最小化后的终态；(5)删去状态集中的所有死状态，即得到化简后的M’。下面我们通过一个例子來看一下该算法中存在的问题。例1假定DFAM如下图1所示：使用上述算法进行化简M:初始划分n0={{0}，{1，2}},此时no含有两个子集II和12,II不可再分，由于I2a=I2b=2ei2，没有新集合增加，故可以得到化简后的M’，如图2所示。1DFAM2DFAM?化简后的M’

6、与原来的M是否等价呢？显然，对于符号串ba，原来的DFAM不能识别，而化简后的M’能够识别，这说明二者并不等价。因为在集合合并的时候没有考虑完全，只是考虑了输入a的情况，而没有考虑输入b的情况，所以上述是错误的。4DNF最小化算法的改进通过分析上述化简过程，我们可以找出算法问题所在。算法步骤2中涉及到集合运算，而忽略了空集对于算法的影响。根据定义3,要判断两个状态是否等价必须对于所有输入符号检查一遍，看它们分别转到等价的状态中，如上面例1中状态1不能接受a而状态2能接受a,显然二者不等价。而在算法中，把状态子集｛1

7、，2｝在接受a后还是转到它自身，所以就出现错误了。某个状态下不能接受某个输入符号即为出错，故上述算法没有考虑到出错情况。因此我们可以对上述算法进行如下改进：(1)增加一个出错状态error,把S划分为终态、非终态、出错三个子集，形成初始划分n;(2)对于n中每个子集Ii，考察每一个aes,Iia=f(Ii，a)特别地如果Ii中某个状态Iij不接受a，则另f(Iij，a)=error。如Iia中的状态分别落于n中P个不同的子集，则子集Ii将被P个更小的状态子集Iil，Ii2,Ojip所细分。令细分后所得的状态集合为n

8、new;(5)删去状态集中的所有死状态和出错状态，即得到化简后的M’。步骤(3)、(4)与原算法相同。使用改进后的分割算法对例1的DFAM秉新进行化简，显然化简得到的M’与原来的M相同，即其本身就是最简的DFA。