On The Quasi-(h, K)-order Memory Linear Finite Automata

Automata theory is a mathematic theory, which essentially researches the functions, the structures, and the relationships between them for discrete mathematics systems, and for the purpose of researching how to analyze and synthesize automata. Analyzing automata means analyzing the functions of a given automata, and synthesizing automata means developing a automata to realize the predetermined functions. Along with the development of the modern science and technology, automata theory has already becomes an important foundation of theory and application for many subjects.The (h, k)-order memory linear finite automata is a typical automata, and it is easily to be developed. Its output is determined by its currently input, by its h inputs just before now and also by its k outputs. The problem about how to construct weakly invertible linear finite automata with delay r can be boiled down to the problem about how to construct weakly invertible finite order memory linear finite automata with delay r. To a given linear finite automata, if it meets some conditions, it can embed into a finite order memory linear finite automata equivalently. All of these are telling us that (h, k)-order memory linear finite automata has an important role in the theory of automata. Our famous scholar Mr. Tao Ren-ji brought forward the notation of the quasi-(h, k)-order memory linear finite automata in [1].If we compare the quasi-(h, k)-order memory linear finite automata to the (h, k)-order memory linear finite automata, they are same in the mode of state transform, but the output of the quasi-(h, k)-order memory linear finite automata is just putting out the first letter of its currently state. But people pay not any attention to it. In this paper, we studied the structure of the quasi-(h, k)-order memory linear finite automata. And at the same time, we studied the invertibility theory of the quasi-(r, r)-order memory linear finite automata, we studied the problem about how to construct a feed-forward invertible linear finite automata with delay r and a feed-forward inverse linear finite automata with delay r with the help of the weakly invertible quasi-(r, r)-order memory linear finite automata. In the end, we studied the decomposition theory of the quasi-(r, r)-order memory linear finite automata.In this paper, we first summarized the main achievements of researchers on the theory of linear finite automat in algebra, then we studied the quasi-(h, k)-order memory linear finite automata. And at the same time, we studied a special finite automata---- the quasi-(r, r)-order memory linear finite automata, we studied the invert theory and the decomposition theory on the quasi-(r, r)-order memory linear finite automata.There are three parts in this paper, each part as a chapter.In chapter one, we introduced the main achievements of researchers on the theory of automata and finite memory automata in algebra, we also introduced chief concepts and notations on the finite automata and the quasi-(h, k)-order memory linear finite automata.Chapter two is some results on the quasi-(h, k)-order memory linear finite automata. In this part, we studied the structure matrices, transfer matrices and free response matrices of the quasi-(h, k)-order memory linear finite automata, and we got a sufficient and necessary condition to determine whether a given quasi-(r, r)-order memory linear finite automata M was a weakly invertible with delay r. We also gave a method to develop a weakly inverse finite automata M′with delay r of the quasi-(r, r)-order memory linear finite automata M . In the end, with the help of the quasi-(r, r)-order memory linear finite automata, we gave a easy way to construct a feed-forward invertible linear finite automata with delay r and feed-forward inverse linear finite automata with delay r. The followings are the main results of the chapter two:Theorem 2.2.1 Let M be the quasi-(h, k)-order memory linear finite automata, determined by (2.2),then the structure matrices of M are as follow:In this theorem E1 ,E2 are the m×mand l×lidentity matrices over the finite field GF ( q ) respectively.Theorem 2.3.1 Let M be the quasi-(r, r)-order memory linear finite automata, determined by(2.3),then M is weakly invertible with delay r if and only if B0 is column independent. Theorem 2.3.2 Let M′=< Y , X , S′,δ′,λ′> be a (r, r)-order memory linear automata, determined by : then M′is a weakly inverse finite automata with delay r of M , where M is a quasi-(r, r)-order memory linear finite automata determined by(2.3). In this theorem Q is m×m invertible matrix.Chapter three is about the decomposition of the quasi-(r, r)-order memory linear finite automata. In this part, we first gave some notations of automata decomposition, and then given any state of the weakly invertible quasi-(r, r)-order memory linear finite automata, we studied the output weight and the strict delay step of the state. In the end of this part, we gave a sufficient and necessary condition to determine whether a given quasi-(r, r)-order memory linear finite automata M is weakly invertible. The condition is that M can be decomposed into M 0and M 1, where M 0is a weakly invertible finite automata with delay 0 and M 1is a weakly invertible quasi-(0, r)-order memory linear finite automata with delay r. The followings are the main results of the chapter three:Theorem 3.2.1 Let M =< X , Y , S ,δ,λ> be a quasi-(r, r)-order memory linear finite automata, determined by(3.1),if M is weakly invertible with delay r ,then :Theorem 3.2.3 Let M =< X , Y , S ,δ,λ> be a finite automata , X = Y = n> 1,if there exists Automata M 0 =< X , X , S 0 ,δ0 ,λ0> and M 1 =< X , Y , S1 ,δ1 ,λ1> with M < M 0 ? M1,where M 0is a weakly invertible finite automata with delay 0 and M 1is a weakly invertible quasi-(0,r)-order memory linear finite automata with delay r ,determined by(3.2),then : (1) ?s∈S, wr , M =| WrM ,s|= 1,| Wr M +1 ,s|= n;(2) ?s∈S, delay ( s )= r.ThusM is weakly invertible with delay r.Theorem 3.2.6 Let M =< X , Y , S ,δ,λ> be a quasi-(r, r)-order memory linear finite automata with delay r, if X = Y = n> 1, then M can be decomposed into M 0and M 1, where M 0is a weakly invertible finite automata with delay 0 and M 1is a weakly invertible quasi-(0,r)-order memory linear finite automata with delay r ,that is M < M 0 ? M1.Theorem 3.2.7 Let M =< X , Y , S ,δ,λ> be a quasi-(r, r)-order memory linear finite automata,| X |= | Y |= n> 1, a sufficient and necessary condition to determine whether M is weakly invertible is that M can be decomposed into M 0and M 1,where M 0is a weakly invertible finite automata with delay 0 and M 1is a weakly invertible quasi-(0,r)-order memory linear finite automata with delay r .