NFA→FA→GFA automaton conversion algorithm

The basic relations and equivalent transformations of non-deterministic finite automata NFA, deterministic finite automata FA, and canonical finite automata GFA are studied; the \"NFA→FA\" equivalent transformation algorithm and the \"FA→GFA\" equivalent transformation algorithm are given, and the existence of FA to GFA is constructively proved, providing a research basis for automaton minimization algorithms. Keywords uncertain automaton; deterministic automaton; gage automaton; equal value transforming algorithm; minimizationAbstract 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; minimumLiterature [1～7] discussed the uncertain finite automata “NFA(Non-Finite Automat) deterministic finite automata→FA(Finite Automat) gauge finite automata→GFA(Gage Finite Automat) However, there are some shortcomings: there are only axiomatic conclusions but no constructive algorithm, and there are some imprecise points in the theoretical proof of the “FA→GFA” equivalent transformation [1]. Therefore, this paper gives the construction, proof and improvement of the “NFA→FA→GFA” automaton automatic transformation algorithm.