| The automata[1 ] theory is a mathematic theory which essentially researches the functions, the structures, and relationships between them for discrete mathematics systems. 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 disciplines such as the control theory, the test for object technique, the nerve network, the security. So it is a vital thing to explore some other new methods for the research of the finite automata.The matrix model for the finite automata is built up in the reference [4] based on references [9],[10],[11]. In the finite automata, M ? I , O , S ,δ,λ, we research it through state flow sheet ,but not through line structure function. We translate I (the input set of M),O (the output set of M),and S (the state set of M) into the Boolean variables X, Z and Q, and then describeδ(the next state function of M) by mapping equation of matrix form Q = B ( x )×Q, and describeλ(the output function of M) by mapping equation of matrix form Z = A( x )×Q.In the end, we obtain the matrix model of M: ( ) x∈X. B ( x ) is called a state-mapping matrix and A( x ) is called a output-mapping matrix.Based on the matrix model of a finite automata and with the tools of Matrix Theory and Boolean Algebra , references[5],[6] not only research and give out some basic algebra natures and physics significance for the state automata ,but also present one new method how to minimize a finite automata. Based on references [4], [5],[6] ,this article go on to research the finite automata with the tools of Matrix Theory and Boolean Algebra. The results obtained are not only suitable to apply the theory of the finite automata to the computer, but also indicate that matrix model plays an important role on research of the application of finite automata.The main conclusions are the following:1. Based on matrix model of the finite automata, I discuss the weak invertibility of the finite automata, then obtain algorithms which judge whether the finite automata and linear finite automata are weakly invertible.2. Based on researching experimental sequences by matrix model, I structure an algorithm, which can obtain the shortest initial state experiment sequence of the minimum linear finite automata, a full and essential condition, which can judge whether a input sequence is a synchronized sequence of the (linear) finite automata, and an algorithm, which can judge whether the linear finite automata have synchronized sequences.3. I discuss the restricted direct product of two finite automatas by its matrix model, and then structure the state-mapping matrix and the output-mapping matrix of the restricted direct product. Further I research this two mapping matrix, then obtain two results of the next state function , operation and two results of the output function , operation.4. I discuss the cascade connection product of two finite automatas by its matrix model, and then structure the state-mapping matrix and the output-mapping matrix of the restricted direct product. Further I research the cascade connection product, and obtain some results: (1) some natures of mapping matrix of the cascade connection product, (2) two results of the next state function , operation, (3) some natures and two results of the output function , operation.This paper consists of five chapters.ChapterⅠ: I introduce the background of the automata theory and the outlook of the finite automata by using the tool of the matrix model, Besides,I give some basic conceptions and symbols of the finite automata and matrix model.ChapterⅡ: I apply the matrix model to the weak invertibility of the finite automata. The results can judge whether the finite automata and linear finite automata are weakly invertible, and if the automata is invertible, I can know how many steps it delays.The main conclusion is the following:Theorem 2.2.4 Let M ? I , O , S ,δ,λbe a linear finite automata, and it, s matrix model is ( ),x∈X, then M is weakly invertible with delayτif and only if if the input alphabets x2 , ,xτ∈Xexist to make the first element of the fist line of A( xh )×B ( xh ?1 )××B ( x1)(1≤h≤τ)is 1 for any input alphabet x1 (≠x0),and if the element which is not zero is the k-th element in the first row of B ( xτ)××B ( x1), then a1 k ( x ) equals zero.ChapterⅢ: I apply the matrix model to the experimental sequence of the finite automata. The results can obtain the shortest initial state experiment sequence of the minimum linear finiteautomata, and judge whether an input sequence is a synchronized sequence of the (linear) finiteautomata. If the linear automata have the synchronized sequence, I can obtain the shortestsynchronized sequences by the results.The main conclusions are the following:Theorem 3.2.1 Let , M- I, O,S,δ,λbe a finite automata, the Boolean quantitiesofl,0 and 5 areX,2 andQ,andM'5 matrix model is,then input SCqllCllCC,15 a synchronized sequence of M if and ouly if the line'rank oftrixTheom be a linear finite automata, and it , s matrixmodel is then the k-word input sequence of M is a synchronizedsequence if and only if matrix (The other elementsare zero).Chapter: I apply the matrix model to the restricted direct product of the finite automata,and structure state-mapping matrix and output-mapping matrix of the restricted direct product.Finally, I research the two mapping matrix and give out results obtained.The main conclusions are the following:Theorem 4.2.2 For any state and input alphabets 1, , t x .. xX, staterow of matrix the following:(The other row , elements are (0,0) ).Theorem 4.3.2 For any state and input alphabets 1, , output alphabet if and only if the (i ? 1)m + j-th row of matrix ) is the following: (The other row , elements areChapterⅤ: I apply the matrix model to the cascade connection product of the finite automata, and structure state-mapping matrix and output-mapping matrix of the cascade connection product.Finally, I research the two mapping matrix and give out results obtained. The main conclusions are the following:Theorem 5.2.2 For any states and input alphabetsstate equals if and only if the -th row of matrix is the ( h ? 1)m + k-th line, The other elements areTheorem 5.4.2 For any states and input alphabets,the last output element of equals Z hif and only if the (i ? 1)m + j-th row of matrix )is the h-th line, The other elements are... |
PDF Full Text Request