Experimental Sequences Of A Kind Of Finite Automata And Product

The automata theory [1] is a mathematic theory which essentially researches the function, the structure ,and relationships between them for discrete mathematic systems studies. With the appearance and development of new technology such as digital computer, digital communication and automation ,the automata theory has already become important theory and application foundation of many subjects. The finite automata theory is an important branch in the automata theory ,and it has significant function in many such as the control theory, the testing for object technique, the nerve network, the security. But the mislinear finite automata theory has the very widespread application in succession domain modelling processes, mathematics system, correspondence , the digital circuit"sets 0", the finite automata equivalence class of recognition of the initial states, the finite automata model's uniform testing, and so on. Therefor the finite automata experimental sequence has the very vital practical significance.Aτ-order weakly inversible finite automata M = X , Y , S ,δ,λcan be decomposed into a weakly inversible finite automata with delay 0 M 0and aτ-order delay unit, namely ( )M ? C M 0 , Mτd when X = Y = n> 1 and WτMs= 1 for any s∈S.But the decomposition of weakly invertible finite automata is very important approach to cryptanalyzing finite automata public-key cryptosystem (FAPKC). Thus Mτd and C ( M , Mτd) play the very vital role in the finite automata decomposition.The experimental sequence which this kind of finite automata and product are studied, We know that two or many finite automata product which the structure relatively single may construct the structure relatively complex some finite automata, but using the simple finite automata nature to reason the complex finite automata nature is an automata theory research commonly used method. This article also discusses experimental sequences of two kind of product of finite automata.The main conclusions are as follows:1 Based on the experimental sequences of a delay unit M d and then -order delay unit M ndand the properties of the finite automata compound operation, the initial (final) state experimental sequence, the synchronous sequence, UIO sequence and D sequence of C ( M , M d) and C ( M , M nd) are studied and a series of properties from them are obtained.2 Based on the properties of the full direct product of finite automata, the initial (final) state experimental sequence,the synchronous sequence,UIO sequence and D sequence of M×Mdand M×Mnd are studied, from them a series of properties are obtained.3 Based on the relation between the full direct product operation and restricted product of finite automata, the properties and the relations of the initial (final) states experimental sequence, the synchronous sequence, UIO sequence , D sequence of M∧Md and M∧Mnd are studied.4 Based on the properties of the finite automata equivalent relation, the weakly isomorphism, the isomorphism,the strong relation, the properties and the relations of experimental sequences between two finite automata are studied when they have those relation respectively.This paper consists of four chapters.ChapterⅠBy introducing the background of the automata theory and the outlook of the finite automata experimental sequence, the basic concepts and symbols of the finite automata experimental sequence are given.ChapterⅡBy applying the finite automata properties of compound operation and the initial (final) state experimental sequence, the synchronized sequence, UIO sequence and D sequence ,the shortest experimental sequence integer determination of C ( M , M d) and C ( M , M nd) are studied.The main conclusions are as follows:Theorem 2.2.2 Ifβ= x1 x2 xk∈X?is an initial or final state experimental sequence of M ,then for any x∈X,α=βx = x1 x2 xk x is an initial or final state experimental sequence of C ( M , M d), thus there are n different initial or final state experimental sequences of C ( M , M d).Theorem 2.3.1 Forβ= x1 x2 xm,βis a synchronous sequence of C ( M , M nd)if and only ifβ≥nandβis a synchronous sequence of M andδ( s1 , L ( ? n ,β))～R ( ? ( m ?n),β) ( ( ))δs2 , L ? n,βfor any s1 ,s 2∈S , where R ( ? n,β)and L ( ? n,β)indicat the words which obtained by removing n character on the left and on the right ofβrespectively.ChapterⅢBy applying the finite automata properties of the full (restricted) direct product operation, the properties of the initial (final) states experimental sequence, the synchronous sequence, UIO sequence, D sequence and the shortest experimental sequence integer determination of M×Md, M×Mnd, M∧Mdand M∧Mndare studied.The main conclusions are as follows:Theorem 3.2.2 For anyα∈X?, ifα≥n, thenαis an initial (final) states experimental sequence, a synchronous sequence, an UIO sequence and a D sequence of M nd= X , X , X n ,δnd ,λn d , and the shortest experimental sequence's length is n , the number of is n n. Moreover, for any ( )s1 , s2 , , sn∈Xn, ( ( ))αλn d s1 , s2 , , sn,αis a UIO sequence of Mn d.Theorem 3.4.1 Forα∈X? withα≥n,αis an initial (final) state experimental sequence or a synchronous sequence or a D sequence of M∧Mnd if and only ifαis an initial (final) states experimental sequence or a synchronous sequence or a D sequence of M .ChapterⅣBy applying the finite automata equivalent relation, the weakly isomorphism, the isomorphism and the strong relation, the relations and properties of experimental sequences between two finite automata when they have those relation separately are studiedThe main conclusions are as follows:Theorem 4.2.2 Let M = X , Y , S ,δ,λand M′= X′, Y′, S′,δ′,λ′be two finite automata, M′= X′, Y′, S′,δ′,λ′be the minimum finite automaton and M～M′.Then(1) Ifα∈X?is a synchronous sequence of M , thenαis a synchronous sequence of M′.(2) Ifα∈X? is a D sequence of M , thenαis a D sequence of M′.(3) Ifαλ( s,α)is a UIO sequence of M , thenαλ′( s′,α) is a UIO sequence of M′, where s∈S ,s′∈S′and s～s′.Theorem 4.2.3 Let M 1 = X 1 , Y1 , S1 ,δ1 ,λ1and M 2 = X 2 , Y2 , S 2 ,δ2 ,λ2be two finite automata and they be weakly isomorphism.Then(1) Forα∈X1?,αis a initial state experimental sequence of M 1if and only if ( )? Xαis a initial state experimental sequence of M 2.(2) Forα∈X1?,αis final state experimental sequence of M 1if and only if ( )? Xαis a final state experimental sequence of M 2.(3) Forα∈X1?,αis a synchronous sequence of M 1if and only if ( )? Xαis a synchronous sequence of M 2.(4) Forα∈X1?,αis a D sequence of M 1 if and only if ( )? Xαis a D sequence of M 2. (5)is a UIO sequence of M 1 if and only if, Xαis a UIO sequence of M₂,where...