NFA→FA→GFA自動機(jī)轉(zhuǎn)換算法

研究了不確定有窮自動機(jī)NFA、確定有窮自動機(jī)FA、規(guī)范有窮自動機(jī)GFA的基本關(guān)系與等價(jià)轉(zhuǎn)換；給出了“NFA→FA”等價(jià)轉(zhuǎn)換算法與“FA→GFA”等價(jià)轉(zhuǎn)換算法，構(gòu)造性證明了從FA到GFA的存在性，提供了自動機(jī)極小化算法的研究基礎(chǔ)。
關(guān) 鍵 詞 不確定自動機(jī); 確定自動機(jī); 規(guī)范自動機(jī); 等價(jià)轉(zhuǎn)換算法; 極小化

Abstract The essential relationship and equal value transformation of Non-Finite Automat, Finite Automat and Gauge Finite Automat (abbreviated as NFA, FA & GFA) is studied. An equal value transforming algorithms of "NFA→FA” and "FA→GFA” are given, the existing nature from FA To GFA is proved by construction, with which the basis of an algorithm research on the minimum of an Automat is provided.
Key words non-finite automat; finite automat; gage automat; equal value transforming algorithm; minimum
文獻(xiàn)[1～7]論及不確定有窮自動機(jī)“NFA(Non-Finite Automat)確定有窮自動機(jī)→FA(Finite Automat)規(guī)范有窮自動機(jī)→GFA(Gage Finite Automat)”等價(jià)轉(zhuǎn)換，但存在不足：僅有公理化結(jié)論，而未見構(gòu)造性算法，且在“FA→GFA”等價(jià)轉(zhuǎn)換理論證明中存在不嚴(yán)謹(jǐn)之處[1]。為此，本文給出“NFA→FA→GFA”自動機(jī)自動轉(zhuǎn)換算法的構(gòu)造、證明與改進(jìn)。