计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
6期
48-51
,共4页
陈矗%任平红%禹继国%马炳先
陳矗%任平紅%禹繼國%馬炳先
진촉%임평홍%우계국%마병선
判定链表%确定有限状态自动机(DFA)%最小化
判定鏈錶%確定有限狀態自動機(DFA)%最小化
판정련표%학정유한상태자동궤(DFA)%최소화
应用判定链表进行DFA最小化方法中只处理无互相依赖等价状态会造成最小化结果不正确.针对此问题,分析了DFA中状态的k次传递等价、含自回路状态的等价以及互相依赖等价等结构特点,将分析结果应用于DFA最小化算法中,提出了一个完善的基于判定链表的DFA最小化算法.该算法涵盖所有等价状态的链表处理,与传统的分割或合并算法的最小化结果一致,保证了基于判定链表的最小化结果的正确性.
應用判定鏈錶進行DFA最小化方法中隻處理無互相依賴等價狀態會造成最小化結果不正確.針對此問題,分析瞭DFA中狀態的k次傳遞等價、含自迴路狀態的等價以及互相依賴等價等結構特點,將分析結果應用于DFA最小化算法中,提齣瞭一箇完善的基于判定鏈錶的DFA最小化算法.該算法涵蓋所有等價狀態的鏈錶處理,與傳統的分割或閤併算法的最小化結果一緻,保證瞭基于判定鏈錶的最小化結果的正確性.
응용판정련표진행DFA최소화방법중지처리무호상의뢰등개상태회조성최소화결과불정학.침대차문제,분석료DFA중상태적k차전체등개、함자회로상태적등개이급호상의뢰등개등결구특점,장분석결과응용우DFA최소화산법중,제출료일개완선적기우판정련표적DFA최소화산법.해산법함개소유등개상태적련표처리,여전통적분할혹합병산법적최소화결과일치,보증료기우판정련표적최소화결과적정학성.
