研究了不確定有窮自動(dòng)機(jī)NFA、確定有窮自動(dòng)機(jī)FA、規(guī)范有窮自動(dòng)機(jī)GFA的基本關(guān)系與等價(jià)轉(zhuǎn)換；給出了“NFA→FA”等價(jià)轉(zhuǎn)換算法與“FA→GFA”等價(jià)轉(zhuǎn)換算法，構(gòu)造性證明了從FA到GFA的存在性，提供了自動(dòng)機(jī)極小化算法的研究基礎(chǔ)。
關(guān) 鍵 詞 不確定自動(dòng)機(jī); 確定自動(dòng)機(jī); 規(guī)范自動(dòng)機(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]論及不確定有窮自動(dòng)機(jī)“NFA(Non-Finite Automat)確定有窮自動(dòng)機(jī)→FA(Finite Automat)規(guī)范有窮自動(dòng)機(jī)→GFA(Gage Finite Automat)”等價(jià)轉(zhuǎn)換，但存在不足：僅有公理化結(jié)論，而未見(jiàn)構(gòu)造性算法，且在“FA→GFA”等價(jià)轉(zhuǎn)換理論證明中存在不嚴(yán)謹(jǐn)之處[1]。為此，本文給出“NFA→FA→GFA”自動(dòng)機(jī)自動(dòng)轉(zhuǎn)換算法的構(gòu)造、證明與改進(jìn)。