一种对无环确定有限自动机化简的高效算法  

作　　者：曾显华[1] 张超[1] 雷向东[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410012

出　　处：《计算机与信息技术》2009年第Z2期64-65,68,共3页Computer & Information Technology

摘　　要：无环确定有限自动机在程序语言的词法分析、命令语句处理、文本模式匹配、信号处理等方面有着重要的应用。若将传统的DFA化简算法用于无环DFA的化简则复杂度较高,本文针对无环DFA在语言识别中的应用,根据语言所识别的单词构造了定义该语言的无环DFA,并给出了针对该语言的无环DFA的化简的高效算法,对算法的复杂度进行了分析,并给出了和传统算法在不同环境下的实验结果,实验结果证明了算法的高效性。

关 键 词：语言识别 DFA的化简 无环 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]