On Input-memory Linear Finite Automata And State Machines

Automata theory is a mathematic theory, which essentially researches the functions, the structures, and the relations between them for discrete mathematics systems. In 1950s, the automata theory was formed on the basic of switch network theory and the Turing machine theory of mathematical logic,which is a branch of mathematics. With the development of science and technology,the automata theory has got deep development and extensive application, become the important foundation of theory and application for many subjects.One of the important questions of automata theory is how to come true. We know any linear finite automaton is able to be imbedded in a linear finite automon with input-memory under some conditions from the document [1]. That is to say, the functions of any linear finite automaton can be realized by the which of a linear finite automaton with input-memory. It proved in the document [2] that any invertibility linear finite automaton with delayÏ„has inverse with delayÏ„which is aÏ„-order linear finite automata with input-memory. And, linear finite automata with input-memory are important to Finete Automaton Public Key Cryptosystem (in short, FAPKC) and digital signatures. Moreover, the linear finite automaton with input-memory is a linear automaton which is typical and easy to realize. So, it is indispensable to study linear finite automata so that we can make more deep researches on any linear finite automata and serve cryptography, network, automatic control, pattern recognition and so on.In this paper, we studied the structures of the linear finite automata with input-memory itself and the products of two linear finite automata with input-memory. It is proved that the sufficient and necessary conditions of a linear finite automaton which have r-order input-memory. Then we discussed the weak invertibility of the linear finite automata with input-memory on the basic of their structure matrixes. The conclusions drawn are as follows:First, we got the sufficient and necessary condition that a linear finite automaton with input-memory is weak invertible with deley 0. Second, we got the sufficient condition that a linear finite automaton with input-memory is weak invertible with deleyÏ„and strict deleyÏ„. Third, we gained a new method to construct a weak invertibile linear finite automaton with input-memory with delayÏ„and strict delayÏ„on the basic of the conclusions drawn above and found a weak inverse of a linear finite automaton with input- memory which is weak invertible with deley 0. Besides, we discussed the weak invertibility of the products of two linear finite automata with input-memory and come to the conclusions that the parallel connection and the composition of two weak invertible input-memory linear finite automata with delay 0 are still input-memory linear finite automata. Furthermore, a new method for determining minimization of linear finite automata with input-memory has been presented in this paper. Then, we got a new minimization method of linear finite automata with input–memory from above. For state machines, the problem parallel with equivalence imdedding is covering of state machines. In this paper, we studied the covering relations between the transformation semigroups of the products of two state machines and the products of their transformation semigroups. The covering relations between various products of two state machines and between two transformation semigroups are proved. Furthermore, some conclusions were drawn that the covering relations between the products of two state machines (transformation semigroups ) and the ones of the other two state machines (transformation semigroups ) which cover them .There are five parts in this paper, each part as a chapter.Chapterâ… :Preface. In this chapter, we introduced the important role of linear finite automata with input-memory played in the automata theory, the main achievements of researchers at home and abroad who applied the linear finite automata with input-memory, chief concepts and notations on (input-memory) the linear finite automaton.Chapterâ…¡:The products on the input-memory linear finite automata. In this chapter, we studied the structure matrixes of the linear finite automata with input-memory . The conclusions were drawn that the products of two linear finite automata with input-memory are still a linear finite automaton with input-memory. The relations of the structure matrixes, free response matrixes and transfer function matrixes between two linear finite automata with input-memory and the products of them were discussed. At last,it was proved that the sufficient and necessary condition of a liner finite automaton which have r-order input–memory.The following are the main results of chapter two:Theorem2.2.4 Let M be a h -order linear finite automaton with input-memory over GF ( q ) and the dimensions of the input and the output be l and m respecyively defined by B′j is a m×l-order matrix over GF ( q ).Then,the structure matrixes A ,B ,C ,D of M are respecyively: Where, 0_{l ,l} represents l×l-order 0 matrix, E_{i ,l} represents the i th l -order unit mayrix, E_l represents l -order unit mayrix.Theorem2.2.10 Let M be a linear finite automaton over GF ( q ),then M have r -order input-memory if and only if M is equivalent to the parallel connection of M₁ and Mα. Where, M₁ is r -order input-memory linear finite automaton , M_αis a linear finite automaton which have r -order input-memory.Theorem2.2.15 Let M = ( X , Y , S ,δ,λ) , M′= (Y , Y′, S′,δ′,λ′) are two h -order linear finite automata with input-memory over GF ( q ),then M·M′= ( X , Y′, S×S′, (δ|—) , (λ|—)) is 2h - order linear finite automata with input-memory.Chapterâ…¢:The weak invertibility of linear finite automaton with input-memory. In this chapter, we discussed the weak invertibility of the linear finite automata with input-memory on the basic of their structure matrixes. The conclusions drawn are as follows:First, we got the sufficient and necessary condition that a linear finite automaton with input-memory is weak invertible with deley 0. Second, we got the sufficient condition that a linear finite automaton with input-memory is weak invertible with deleyÏ„and strict deleyÏ„. Third, we gained a new method to construct a weak invertibile linear finite automaton with input-memory with delayÏ„and strict delayÏ„on the basic of the conclusions drawn above and found a weak inverse of a linear finite automaton with input- memory which is weak invertible with deley 0. Besides, we discussed the weak invertibility of the products of two linear finite automata with input-memory and come to the conclusions that the parallel connection and the composition of two weak invertible input-memory linear finite automata with delay 0 are still input-memory linear finite automata.The following are the main results of chapter three:Theorem3.2.2 Let M be a h -order linear finite automaton with input-memory over GF ( q ) defined by then(1)M is weak inversible with delay 0 if and only if the structure matrix D of M is linear irrelevant of column.(2)when 1≤τ≤h,if B_j= 0, j = 0,1,Ï„- 1,then M is weak inversible with srict delayÏ„if and only if B_Ï„is linear irrelevant of column.Corollary 3.2.3 Let M be a h -order linear finite automaton with input-memory over GF ( q ) defined by then(1)If B0 is linear irrelevant of column,thenM is weak inversible with delayÏ„.Ï„is any nonnegative integers.Construct 3.3.1 We can construct M which is a weak inversible h -order linear finite automaton with input-memory over GF ( q ) with strict delayÏ„.The method is:let M be defined by B_j is a m×l-order matrix over GF ( q ).Let B₀ = B₁ =…= B_Ï„-1 = 0,BÏ„is a m×l-order matrix over GF ( q ) which is linear irrelevant of column, B_Ï„+1 ,…, B_h are arbitrary m×l-order matrixes over GF ( q ).Then M is a weak inversible h -order linear finite automaton with input-memory over GF ( q ) with strict delayÏ„. Here, 1≤τ≤h.Construct 3.3.2 We can construct M which is a weak inversible h -order linear finite automaton with input-memory over GF ( q ) with delayÏ„.The method is:let M be defined by B_j is a m×l-order matrix over GF ( q ). Let B0 is a m×l-order matrix over GF ( q ) which is linear irrelevant of column, B₁ , B₂ ,…, B_h are arbitrary m×l-order matrixes over GF ( q ).Then M is a weak inversible h -order linear finite automaton with input-memory over GF ( q ) with delayÏ„. Here,Ï„is any nonnegative integers.Theorem3.4.1 Let M = ( X , Y , S ,δ,λ) be a h -order linear finite automaton with input- memory over GF ( q ) defined by If M is weak inversible with delay 0, then there exist a (0,4) -order memory linear finite automaton M′= (Y , X , S′,δ′,λ′) which is weak inverse with delay 0 of M . M′is defined by Where, P is left inverse matrix of B₀ .Theorem3.5.1 Let M = ( X , Y , S ,δ,λ), M′= ( X′, Y′, S′,δ′,λ′) be two h -order linear finite automata with input-memory over GF ( q ) defined by respectively: If M and M′are all weak inversible with delay 0, then the full direct product M×M′= (X×X′, Y×Y′, S×S′,δ×δ′,λ×λ′) is weak inversible with delay 0 too.Theorem3.5.2 Let M = ( X , Y , S ,δ,λ) , M′= (Y , Y′, S′,δ′,λ′) be two h -order linear finite automata with input-memory over GF ( q ) defined by respectively: The input and output dimesions of M are l and m respectively. The input and output dimesions of M′are m and m′respectively. If M and M′are all weak inversible with delay 0, then the composition M·M′= ( X , Y′, S×S′,δ,λ) is weak inversible with delay 0 too.Chapterâ…£:Minimizing on the input-memory linear finite automata.In this chapter, a new method for determining minimization of linear finite automaton with input-memory has been presented. Then, we got a new minimization method of a linear finite automaton with input- memory from above.The following are the main results of chapter four:Theorem4.2.8 Let M = ( X , Y , S ,δ,λ) be a h -order linear finite automaton with input- memory over GF ( q ) defined by M is minimal if and only if the column of U is linear irrelevant over GF ( q ).Where,U is a matrix composed of linear coefficient of M ,Theorem4.2.11 Let M = ( X , Y , S ,δ,λ) be a h -order linear finite automaton with input- memory over GF ( q ) defined byThe structure matrixes of M are A , B , C , D . If column j₁ , , jr of U is linear irrelevant maximal and constitute matrix U₁, U = U₁T,T is r×n-order matrix over GF ( q ). Let M₁ is a linear finite automaton over GF ( q ). Its structure matrixes are A₁ = TA′, B₁ = TB, C₁ = C′,D₁ = D. A′and C′are the matrixes composed of column j₁ ,…, j_r of A and C .Then M～M₁ and M is minimal.Chapterâ…¤:Covering relations of the products on state machines and transformation semigroups. In this chapter, we studied the covering relations between the transformation semigroups of the products of two state machines and the products of their transformation semigroups. The covering relations between various products of two state machines and between two transformation semigroups are proved.Furthermore,some conclusions were drawn that the covering relations between the products of two state machines (transformation semigroups ) and the ones of the other two state machines (transformation semigroups ) which cover them .The following are the main results of chapter five:Theorem 5.2.3 Let M =(Q ,∑, F ), M′= (Q′,∑′, F′) are two state machines, then(1) M∧M′≤M×M′(2) M×M′≤M(?)M′(3) MωM′≤M(?) M′Theorem5.2.4 Let M =(Q ,∑, F ), M′= (Q′,∑′, F′) are two state machines, then(1) TS ( M∧M′) = TS ( M )∧TS(M′),for epimorphismsθ:∑⁺â†'S ,θ′:∑⁺â†'S′. Where,θ(α) = [α],θ′(α) = [α]′.(3) TS ( M(?) M′)≤TS ( M )(?) TS(M′)Theorem 5.2.6 Let Mi =(Q_i ,∑_i , F_i ), M_i′= (Q_i′,∑_i′, F_i′), i=1,2 are state machines. If M₁≤M₁′, M₂≤M₂′,then(1) M₁×M₂≤M₁′×M₂′(2) M₁(?) M₂≤M₁′(?) M₂′(3) M₁ωM₂≤M₁′ωM₂′...