| 基于信息系统的确定有限自动机最小化算法 |
| |
| 引用本文： | 杨传健,葛浩,姚光顺,王波. 基于信息系统的确定有限自动机最小化算法[J]. 计算机应用, 2012, 32(7): 1991-1993. DOI: 10.3724/SP.J.1087.2012.01991 |
| |
| 作者姓名： | 杨传健 葛浩 姚光顺 王波 |
| |
| 作者单位： | 1. 滁州学院 计算机与信息工程学院，安徽 滁州2390122. 滁州学院 机械与电子工程学院，安徽 滁州239012 |
| |
| 基金项目： | 安徽高等学校省级自然科学研究项目，安徽省高等学校省级优秀青年人才基金，滁州学院科学研究项目 |
| |
| 摘 要： | 目前，确定有限自动机(DFA)最小化问题多侧重于理论研究，尚无太多便于实现的算法，为此，对确定有限自动机最小化方法进行了研究，提出将DFA转换为信息系统，基于等价类划分方法简化信息系统，再将简化的信息系统转换为最小化DFA；针对上述处理过程，给出一个基于分治思想的DFA最小化算法，在平均情况下该算法的时间复杂度为O(n log n)，空间复杂度为O(n)。最后通过实例验证了所提算法的正确性。
|
| 关 键 词： | 确定有限自动机 信息系统 等价类 最小化 |
| 收稿时间： | 2012-01-06 |
| 修稿时间： | 2012-02-20 |
Algorithm for minimizing determination finite automation based on information system |
| |
| YANG Chuan-jian , GE Hao , YAO Guang-shun , WANG Bo. Algorithm for minimizing determination finite automation based on information system[J]. Journal of Computer Applications, 2012, 32(7): 1991-1993. DOI: 10.3724/SP.J.1087.2012.01991 |
| |
| Authors: | YANG Chuan-jian GE Hao YAO Guang-shun WANG Bo |
| |
| Affiliation: | 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 |
| |
| 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. |
| |
| Keywords: | Determination Finite Automation(DFA) information system equivalence classes minimization |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
