Some Results Of Finite Automata Invertibility

The main domains of automata theory include the function, structure and relation of the discrete digital system. With the development of electronic technology and the information theory, automata theory goes into every area of information technology, and provides theoretical models, design technology and algorithm to them. The invertibility of finite automata is one of the areas in automata theory and it has been studied since the concepts of the information lossless and the information lossless of finite order were proposed. The proposition and application of the finite automata public key cryptosystem stimulates the investigation of invertibility of finite automata. In this thesis, several results are given in the areas of the invertibility of finite automata.The main work of this thesis contains three parts: the invertibility of finite automata on matrix ring, the structure of feedforward inverse finite automata and weakly invertible finite automata, and the decomposition of weakly invertible finite automata.In the first part, we study the invertibility of finite automata over a matrix ring. Matrix ring is a typical noncommutative ring and it has fine structure and lots of achievement. We get the following result: Let M be a QL-type finite automaton over a matrix ring and M the corresponding linear finite automaton of M over the basic field, then M is weakly invertible with delay τ if and only if M is weakly invertible with delay T. Therefore, the invertibility of finite automata over a matrix ring is transformed into the invertibility of finite automata over a field. Then, we give some results of the invertibility of finite automata over a matrix ring.In the second part, we study the structure of feedforward inverse finite automata in general case, and we also discuss the structure of weakly invertible finite automata. A form of structure of feedforward inverse finite automata with delay r is given in the situation that C(Ma, f) i.s a c-order semi-input-memory finite automata where autonomous finite automaton Ma = is cyclic and the number of input alphabet set is equal to the number of output alphabet set. We also discuss a form of structure of feedforward inverse finite automata with delay T in the situation that the number of input alphabet set is different to the number of output alphabet,set. At last, we give a form of structure of weakly invertible finite automata with delay r, and an algorithm to construct the n-ary weakly invertible finite automata with delay 2.In the third part, we study the decomposition of weakly invertible finite automata. First, we present an algorithm to decompose a kind of weakly invertible finite automata with delay 2 satisfied the special condition. Then we extend this algorithm so that we can decompose a kind of weakly invertible finite automata with delay r satisfied the special condition. Next, we give an algorithm to attack the finite automata public key cryptosystem. At last, we analyse the time complexity of the algorithm. The time complexity of this attack algorithm is O(pmτ-m-r1-r2-....rτ-|S|). So, the finite automata public key cryptosystem can resist this attack under the computation power of the computer now.