计算机应用 ›› 2012, Vol. 32 ›› Issue (07): 1991-1993.DOI: 10.3724/SP.J.1087.2012.01991

• 人工智能 • 上一篇    下一篇

基于信息系统的确定有限自动机最小化算法

杨传健1,葛浩2,姚光顺1,王波2   

  1. 1. 滁州学院 计算机与信息工程学院,安徽 滁州239012
    2. 滁州学院 机械与电子工程学院,安徽 滁州239012
  • 收稿日期:2012-01-06 修回日期:2012-02-20 发布日期:2012-07-05 出版日期:2012-07-01
  • 通讯作者: 杨传健
  • 作者简介:杨传健(1978-),女,安徽来安人,副教授,硕士,CCF会员,主要研究方向:数据挖掘、信息处理、粗糙集理论;葛浩(1976-),男,安徽滁州人,副教授,硕士,CCF会员,主要研究方向:数据挖掘、粒计算、粗糙集理论;姚光顺(1982-),男,安徽全椒人,讲师,硕士,主要研究方向:人工智能、信息融合。
  • 基金资助:

    安徽高等学校省级自然科学研究项目(KJ2011Z276;KJ2012A212);安徽省高等学校省级优秀青年人才基金资助项目(2011SQRL123;2012SQRL151);滁州学院科学研究项目(2010kj014B; 2011kj003Z; 2011kj017B)

Algorithm for minimizing determination finite automation based on information system

YANG Chuan-jian1,GE Hao2,YAO Guang-shun1,WANG Bo2   

  1. 1. School of Computer and Information Engineering, Chuzhou University, Chuzhou Anhui 239012, China
    2. School of Mechanical and Electronic Engineering, Chuzhou University, Chuzhou Anhui 239012, China
  • Received:2012-01-06 Revised:2012-02-20 Online:2012-07-05 Published:2012-07-01
  • Contact: YANG Chuan-jian

摘要: 目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行了研究,提出将DFA转换为信息系统,基于等价类划分方法简化信息系统,再将简化的信息系统转换为最小化DFA;针对上述处理过程,给出一个基于分治思想的DFA最小化算法,在平均情况下该算法的时间复杂度为O(n log n),空间复杂度为O(n)。最后通过实例验证了所提算法的正确性。

关键词: 确定有限自动机, 信息系统, 等价类, 最小化

Abstract: At present, Determination Finite Automation (DFA) minimization more focuses on theoretical research, and there are not many algorithms easy to achieve. Therefore, the method of minimization of determination finite automation was researched. First, DFA was converted into information system; and then the information system was simplified, which was based on the partition of equivalence classes; at last the simplified information system was converted into minimized DFA. Concerning the above process, an algorithm of minimizing DFA based on strategy of divide and conquer was proposed. In the average case, the time complexity and space complexity of the algorithm are O(n log n) and O(n) respectively. Finally, an example was used to explain the feasibility of the proposed algorithm.

Key words: Determination Finite Automation (DFA), information system, equivalence classes, minimization

中图分类号: