计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2012年
7期
1991-1993,1997
,共4页
杨传健%葛浩%姚光顺%王波
楊傳健%葛浩%姚光順%王波
양전건%갈호%요광순%왕파
确定有限自动机%信息系统%等价类%最小化
確定有限自動機%信息繫統%等價類%最小化
학정유한자동궤%신식계통%등개류%최소화
目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行了研究,提出将DFA转换为信息系统,基于等价类划分方法简化信息系统,再将简化的信息系统转换为最小化DFA；针对上述处理过程,给出一个基于分治思想的DFA最小化算法,在平均情况下该算法的时间复杂度为O(n log n),空间复杂度为O(n).最后通过实例验证了所提算法的正确性.
目前,確定有限自動機(DFA)最小化問題多側重于理論研究,尚無太多便于實現的算法,為此,對確定有限自動機最小化方法進行瞭研究,提齣將DFA轉換為信息繫統,基于等價類劃分方法簡化信息繫統,再將簡化的信息繫統轉換為最小化DFA；針對上述處理過程,給齣一箇基于分治思想的DFA最小化算法,在平均情況下該算法的時間複雜度為O(n log n),空間複雜度為O(n).最後通過實例驗證瞭所提算法的正確性.
목전,학정유한자동궤(DFA)최소화문제다측중우이론연구,상무태다편우실현적산법,위차,대학정유한자동궤최소화방법진행료연구,제출장DFA전환위신식계통,기우등개류화분방법간화신식계통,재장간화적신식계통전환위최소화DFA；침대상술처리과정,급출일개기우분치사상적DFA최소화산법,재평균정황하해산법적시간복잡도위O(n log n),공간복잡도위O(n).최후통과실례험증료소제산법적정학성.
