Discussions On The Finite Automata Based On Its Matrix Model

The automata theory is a mathematic theory which essentially researches the functions, the structures, and the relationships between them for discrete mathematics systems. With the rapid development of science and technology such as micro-electron and information, the automata theory is getting to permeate into different fields and has already become the important foundations of theory and application for many subjects. The finite automata theory is an important branch in the automata theory. It is an important tool for the researches of many fields such as the control theory, the test for object technique, the cell automata, the security[11~14]. So it is an important thing to find some other new theoretic method for the research of the finite automata.A new mathematical model for the finite automata, matrix model, is built up in the reference[ 6 ]. A finite automata, sayÎœ, means a quintupleΙ,Ο,S ,δ,λ, whereΙis a nonempty finite set (the input alphabet ofÎœ),Οis a nonempty finite set (the output alphabet ofÎœ), S is a nonempty finite set (the state alphabet ofÎœ),δ:S×Ιâ†'S a single-valued mapping(the next state function ofÎœ) andλ:S×Ιâ†'Οa single-valued mapping(the output function ofÎœ). We translateΙ,Ο, S into the Boolean variablesΧ,Ζ, Q, then describeδby the mapping equation of matrix form Q=Î'( x)×Q andλby the mapping equation of matrix formΖ=Α( x)×Q.Finally we get the matrix model of the finite automataÎœ:( x∈Χ).Α( x) is called the Boolean-output-mapping matrix andÎ'( x) is called the Boolean-state- mapping matrix.Based on the matrix model of a finite automata and with the tools of Matrix Theory and Boolean Algebra, paper [7~9] not only research and give out some basic algebra for the matrix model of the state automata, but also present two new methods on how to determine the equivalence between the finite automata and how to minimize a finite automata. These methods have the advantage of designing algorithm and handling problems on computer, which are useful to research and develop the theory of the finite automata.