计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2011年
1期
70-73
,共4页
任平红%陈矗%曹宝香%禹继国
任平紅%陳矗%曹寶香%禹繼國
임평홍%진촉%조보향%우계국
子集构造法%非确定有限自动机%优化的%确定化算法
子集構造法%非確定有限自動機%優化的%確定化算法
자집구조법%비학정유한자동궤%우화적%학정화산법
使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题.为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法.首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量.相比子集构造法,算法能更有效地对非确定有限自动机进行确定化.
使用子集構造法對非確定有限自動機進行確定化的過程中存在大量重複計算的問題.為解決此問題,基于非確定有限自動機的特點併針對子集構造法的不足,提齣瞭一種優化的非確定有限自動機確定化算法.首先定義瞭識彆符的有效引齣狀態集概唸併證明瞭ε-closure的併定理以保證算法的正確性,其次給齣瞭用于避免重複計算的識彆符的有效引齣狀態集的構造子算法和單狀態集的ε-closure的求算子算法,基于這兩箇子算法給齣瞭優化的非確定有限自動機確定化算法,最後將算法應用于實例,實驗結果錶明計算量遠小于子集構造法的計算量.相比子集構造法,算法能更有效地對非確定有限自動機進行確定化.
사용자집구조법대비학정유한자동궤진행학정화적과정중존재대량중복계산적문제.위해결차문제,기우비학정유한자동궤적특점병침대자집구조법적불족,제출료일충우화적비학정유한자동궤학정화산법.수선정의료식별부적유효인출상태집개념병증명료ε-closure적병정리이보증산법적정학성,기차급출료용우피면중복계산적식별부적유효인출상태집적구조자산법화단상태집적ε-closure적구산자산법,기우저량개자산법급출료우화적비학정유한자동궤학정화산법,최후장산법응용우실례,실험결과표명계산량원소우자집구조법적계산량.상비자집구조법,산법능경유효지대비학정유한자동궤진행학정화.
