| Automata theory is a mathematic theory, which essentially researches the functions,the structures,and the relationships between them for discrete mathematics systems. In 1950s, on the basic of switch network theory and the Turing machine theory of mathematical logic, it formed the automata theory, which is a branch of mathematics. At present, according to the application situation of the automata theory, It focuses on the invertible automaton, linear automaton and cycle automaton.In 1985, Chinese researcher Tao Renji first proposed the Finite Automaton Public Key Cryptosystem (in short, FAPKC). As the theory has the valuable application in constructing the cryptosystem of single key or a pair of keys and cryptosystem which is based on identify and some other important branchs of cryptography, It has wonderful potential applications in the future, which inspires the researchers' interest.In the construction of cryptosystem of a pair of keys and the cryptosystem which is based on identify, the composition of finite automaton becomes a basic means. To my knowledge, There aren't other papers that discuss the properties of the composition of finite automaton, besides the documents [3~5], which deeply researched the relationships of the invertibility and the RaRb transformations between two finite automatons and their composition. And I have done a series of reseaches of the relationships of the weak inverse, the strict delay step, minimality and linearity between two finite automatons and their composition. The results I obtained may have important value in the construction of cryptosystem in constructing the finite automaton which has the properties we need.The main conclusions are the following:1.On the strict delay step: let Mi be a weakly invertible automaton on X, whose strict delay step is (i ,i=1,2, then M1·M2 must be a weakly invertible automaton with delay (1+(2[4],let its strict delay step be (, we have (1((((1+(2; if (1=0, then M1· M2 and M2·M1 is a weakly invertible automaton whose strict delay is (2; in general, we obtained a sufficient and necessary condition for M1·M2 being a weakly invertible automaton whose strict delay step is (1+(2.2.On the weak inverse: 1) if M1' is a weak inverse with delay ( of M1, and M2' is a weak inverse with delay 0 of M2, then M2'·M1' must be a weak inverse with delay ( of M1· M2 ; 2) if M1' is an inverse with delay ( of M1, and M2' is a weak inverse with delay (' of M2, we obtained a sufficient condition for M2'· M1' being a weak inverse with delay (+(' of M1· M2.3.On the minimality: It infers to that two finite automatons must be minimal,if their composition is minimal. We illustrate that two finite automatons are minimal, but their composition is not minimal.4.On the linearity: The composition of linear finite automaton must be linear, and we have the manifest formulas of their construct matrices, free response matrices and transfer function matrices.Furthermore,one of the important questions of automata theory is how to come true. So we research the technology of linear realization of general automaton, the linear finite automaton with memory(input-memory) is a linear automaton with simple structure which is typical and easy to realize.the document [33] gave some sufficient and necessary conditions for M being able to be imbedded in a linear finite automaton with memory, a sufficient condition for M being able to be imbedded in a linear finite automaton with memory and a sufficient condition that M cannot be imbedded in any linear finite automaton with memory respectively. As we know, "being imbedded in" means that the function of the latter must be stronger than the formers, even by far , that is to say that the latter can perform the former's function, but it maybe waste much more. So which kind of finite automaton is equivalent to a linear finite automaton in the function ?in other words , which kind of complicate linear finite automaton has the same function as a linear finite automaton with memory(input-memory)?We used the module th... |
PDF Full Text Request