A Study Of Algebraic Representation Of Automata And Formal Languages

The theory on automata and formal languages is an important foundation of computer science. It has comprehensive applications in information science, biological science, management science and so on. Based on the algebraic theory of automata and formal languages. In algebraic point of view, we study representation of automata, algebraic structure of formal languages and minimization of weighted automata.The main tasks of this dissertation are as follows:(1) The problems about the classification of canonical Sl-automata and canonical C-automata are solved, respectively.Firstly, we deal with structure of cyclic monoid-matrix type automata and regular monoid-matrix type automata. Secondly, we provide a method to determine structure of canonical Sl-automata (canonical C-automata, resp.) whose endomorphism monoids are isomorphic to a given finite meet semilat-tice with the greatest element (Clifford monoid, resp.). Finally, we consider the characteristic monoids and quotient automata of the monoid-matrix type automata. We deal with relationship between endomorphism monoids and characteristic monoids. Also, we give a characterization of the quotient au-tomaton in terms of monoid homomorphisms.(2) The generalized normal automata and generalized canonical automata are introduced and studied. Also, we deal with the relation between them and their primary automata.Firstly, we define generalized normal automata and generalized canonical au- tomata by the minimal generated set. Secondly, we deal with relationship between generalized normal automata and the primary automata. We finally study the quotient automata of generalized canonical automata.(3) Three classes of formal languages related with binary relations are intro-duced. Their algebraic characterizations and decision problems are studied.Firstly, we introduce three binary relations:<Oi,<Li,<Ri. Their indepen-dent sets are denoted by Oi(?), Li(?),Ri(?), respectively. Secondly, the combinatorial properties and algebraic characterizations of these languages are established. By equipping them with two binary operations, respectively, these classes of languages form semilattice-ordered semigroups. It is shown that they are freely generated by E in three subvarieties of semilattice-ordered semigroups, respectively. Finally, it is shown that the decision problems on these languages are P-Problems and the word problems for three subvarieties are solvable.(4) The Homomorphism Theorem and Isomorphism Theorem over determin-istic weighted finite automata are given. We construct a uniqueness minimal automaton for any given regular formal power series.