确定有穷自动机最小化算法的研究

确定有穷自动机最小化算法的研究计科0803姜斌2007401091.《对确定有限自动机最小化算法的改进》的错误指正在阅读了在《桂林航天工业高等专科学校学报》2005年第4期，由徐红老师发表的《对确定有限自动机最小化算法的改进》一文后，我发现徐老师在分析DFA最小化的过程中出现了错误。原文提到的“确定有限自动机的化简算法(DFA极小化算法)”，即所谓的原始算法，原文中对于算法的描述是这样的：(1)首先把状态集S分成终态集和非终态集,因为终态集可接受ε,而非终态集则不能,所以他们是可区分的。这就是基本划分:π={Q,K-Q}。(2)假定经过k次划分后,已含有m个子集,π={I1,I2,⋯,Im},则对每一个Ii和每一个a∈Σ。考察:Iia=f(Ii,a),如Iia中的状态分别落于π中P个不同的子集,则子集Ii将被P个更小的状态子集Ii1,Ii2,⋯,Iip所细分。令细分后所得的状态集合为πnew。(3)重复步骤2,直到直至所含的子集数不再增加为止。即πnew=π。(4)对π中的每个子集Ii,若该子集包含原有的初态,则此代表状态便为最小化后M的初态;若该子集包含原有的终态,则此状态便为最小化后M的终态。(5)删去状态集中的所有死状态。徐老师认为，该算法在刚开始只是简单地将状态集分成了终态集和非终态集两个部分，而忽视了初始状态的特殊地位，于是徐老师认为应该将初始状态单独作为一个集合，在完成了所有集合的划分之后再与最近的集合进行合并的判断。并且徐老师还举了一个例子来说明。给定如图1.1所示的确定有穷自动机。图1.1徐老师在使用原始算法分析时，给出如下分析“因为{0,1}a={1}∈{0,1};{0,1}b={2}∈{2,3}，所以{0,1}不用再划分。”很显然，徐老师在分析“{0,1}b={2}∈{2,3}”时发生了错误。原DFA中0状态点并没有经过b到达的状态，而1状态有经过b可达的一个终态2，显然b这个串可以区分0与1这两个状态，也就是说0与1应该划分。而徐老师由于这个错误的产生，导致了对原算法的理解出错。而徐老师提出的将原初态作为单独一个集合的做法，我认为是完全没有必要的，所谓的改进算法只不过是额外地增加操作量罢了。不过原算法确实存在着初始集合的划分问题，下文中会给出一种解决方案。2.对《一种将NFA到最小化DFA的方法》的学习与研究a)方法引入由毛红梅，聂承启两位老师在计算机与现代化2004年第10期上发表的《一种将NFA到最小化DFA的方法》一文中提到了一种将DFA最小化的方法，即“用树型分割法实现从DFA到最小化DFA的转化”，其具体实现如下：(1)首先将DFA所有的状态分割成可接受状态和不可接受状态集;(2)用双圆圈来标记最大等价状态集;(3)将DFA所有输入字母按某一顺序排列;(4)依次输入字母进行判断,直到求出最大集为止。如图2.1所示。图2.1图2.2这种做法较《编译原理》一书上所讲述方法而言更为直观，故而我采用了这种方法并尝试实现，在实际编程过程中发现，有几个很重要的地方两位老师并没有提到。所以我在此提出我的实现，作为补充。第一，有些状态对于某些输入字母并不是都有下个状态，即会出现输入字母无到达状态的情况。第二，初始集合如何确定划分。第三，具体如何划分集合。b)我的实现第一，有些状态对于某些输入字母并不是都有下个状态，即会出现输入字母无到达状态的情况。对于这种情况，我的解决办法是在新状态组中增加一个“空状态”，并将其置于新状态集合的最开始。当出现输入无到达状态时就指向该“空状态”，这样在进行集合划分的时候就有了比较的具体数值，更易于实现。第二，初始集合的划分。文中只是简单地提到将初始集合划分为接受状态和不可接受状态，即终态和非终态，然而这样的划分会遇到新状态集合的初始态位置不确定的情况。故而，需要注意的一点是，原初始态应该先确定放于新状态集合中的开始位置，在我的实现中，是将原初始态默认放于“空状态”的下一个位置，并且把有相同属性（终态或非终态）的状态一齐放入，而将剩余的状态放入第三个位置。如图2.2所示。第三，如何划分集合。两位老师只是很简单地提到，对于输入字母到达的下一个状态处于不同的状态集合中就需要对该组状态进行划分。我的实现是，先取出需要处理的一个状态集合s中所有状态并放入临时状态组t中，如果只有一个状态则直接跳过，如果有多个，则逐个进行输入判断。判断时，首先将第一个状态放回状态集合中，并将其在新状态组中指向的状态m保存起来，对于其后的所有状态，对于该输入若也指向m，则将其放入s，并从t中删去，当扫描完所有t中状态后，看t中是否有状态剩余，若有，说明剩下的状态与第一个状态指向的状态集合不同，即不等价，需要被划分。所以在新状态集合中新建一个状态组，并将t中剩余状态加入其中。第四，状态的指向。由于新状态组需要不断划分，也就相当于状态名会不断改变，所以在未完成状态划分之前是不需要考虑每个状态的指向的。在确定了所有的划分之后，再通过一次对每个划分中第一个状态的边的遍历，对新状态的边进行确定。故而实际执行过程如下：（1）建立新状态集合state，将state[0]置为空状态。（2）将原初始状态放入state[1]中，并将与原初始状态有相同属性（终态或非终态）的状态一齐放入state[1]中。（3）将剩下状态放入state[2]中。（4）以字母输入为循环开始，对新状态集合进行遍历（除了空状态），遍历过程如下：（a）取出state[i]中所有状态，放入临时状态组t中（b）查看t中状态数，大于一则继续（c）将t[0]放回state[i]中，并保存t[0]经过输入字母到达的状态m。（d）遍历t中剩余状态，如果经过输入字母也到达m，则放入state[i]中，并从t中删除，否则直接跳过。（e）若t中有剩余状态，则在state中新加一个状态，并将t中所有剩余状态加入。（5）遍历state中状态集合中的第一个状态，对于每个输入所到达的在state中的状态进行记录，以确定state状态组的边。在实际运行中发现，该法亦能正常处理全是终态的DFA。参考文献[1]徐红.对确定有限自动机最小化算法的改进[J].桂林航天工业高等专科学校学报,2005(4).[2]毛红梅,聂承启.一种将NFA到最小化DFA的方法[J].计算机与现代化,2004(10).[3]AlfredV.Aho,RaviSethi,JeffreyD.Ullman,贝尔实验室,Avaya实验室,斯坦福大学著.编译原理[M].–北京：机械工业出版社,2003.