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