Synchronous Sequences And UIO Sequences Of Finite Automata

Automata theory is a mathematic theory ,which essentially researches the functi- ons, the structures, and the relationships between them for discrete mathematics.With the development of science and technology ,the automata theory has got deep develo- pment and extensive application ,become the important foundation of theory and application for many subjects.At present, according to the application of automata ,the researches are concentrating mainly on linear automata and automata on modelling.In this paper, we first summarized the main achievements of researchers on (linear) finite automata theory in algebra. Then we studied the synchronous sequences of linear finite automata. And at the same time ,we also studied the UIO sequences of linear finite automata. At last, we studied the synchronous sequences and UIO sequences of finite automata after product operation.There are four parts in this paper, each part as a charpter.In charpter one ,we introduced the main achievements of researchers in algebra ,chief concepts and notations on (linear) finite automata.In chapter two we discussed the synchronous sequences of linear finite automata, gave sufficient and necessary condition that linear finite automata has the sequences. We also discussed the synchronous sequences of two kinds of automata———Input-Memory Linear Automata and the minimal linear automata which are imbedded in linear finite automata with input-memory . At last, we also gave some algorithms on the existence of synchronous sequences of linear finite automata and generating the (minimal) synchronous sequences when it has the sequences.The main conclusion are the following:Theorem 2.2.7 Let M =< X , Y , S ,δ,λ> be a linear finite automata over GF ( q ) and the dimension of vector space S be n ,then the following statements are equivalent:(1) M has synchronous sequences;(2) S n = {0 s};(3)δ( si ,0 x n) = 0sfor ?s i∈S (i = 1,2, , n), and s1 , s 2, , s nare the basis of vector space.