Cyclic Finite Automata And Path Algebras Of Finite Automata

Automata theory is a mathematical theory, which essentially studies the functions, the structures of discrete mathematics systems and the relations between them.It aims to analyze and synthesize automata. The theory of finite automata is a branch of automata theory. With the development of science and technology such as digital computer, digital communications and automation, the theory of finite automata plays an increasingly important role in theory and practice.In this paper , (weakly) invertibility and decomposition of cyclic finite automata are discussed, algebraic properties of cyclic finite automata are studied by use of algebraic methods, and the relationship between properties of finite automata and algebraic properties of path algebras of finite automata is discussed.This paper is composed of five parts , each part of the former four parts is as a chapter, and the last part is the concluding remarks.In chapter 1, some applications of finite automata and the main work in this paper are introduced, and some basic concepts and notions on finite automata are given.In chapter 2, (weakly) invertibility and decomposition of cyclic finite automata are discussed. The main results are as follows:Theorem 2.1.1 Let M =< X, Y,S,δ,λ> be a cyclic finite automaton and s0∈S be a generator of M . Then M is weakly invertible if and only if s0 is weakly invertible.Theorem 2.2.2 Let M =< X, Y,S,δ,λ> be a cyclic finite automaton generated by s0 , and M be weakly invertible with delayτ. Suppose | X |=| Y|=n>1, then M can be decomposed into a WIFA with delay 0 and aτ-order delay unit if and only if | WτM,s0|= 1.In chapter 3, properties of homomorphism of finite automata and endomorphism of a cyclic finite automaton are studied. An algorithm of finding the endomorphism semigroup and the automorphism group of a cyclic finite automaton is given, and it is proved that every finite automaton is a homomorphism image of a direct sum of cyclic finite automata. The main results are as follows:Theorem 3.1.1 Let M =< X, Y,S,δ,λ> be a cyclic finite automaton with s0 as a generator, letπ0 be a right congruence on X ? with respect to s0 . Then Theorem 3.1.3 Every endomorphism of is left multiplication by an element Conversely, left multiplication by an element ofφ(α0)is an endomorphism of In other words,Theorem 3.1.4 Automorphisms of are determined by That is is an automorphism of if and only if f is left multiplication by an element ofTheorem 3.2.4 Let M be a finite automaton, then M is a homomorphism image of a finite automaton which is a direct sum of a finite number of cyclic finite automata.In chapter 4, the relationship between properties of finite automata and algebraic properties of their path algebras is discussed. The main results are as follows: Theorem 4.2.1 Let M =< X, Y,S,δ,λ> be a finite automaton and M₁ =< X , Y , S1 ,δ1,λ1 > be a sub-automaton of M . ThenTheorem 4.3.1 Let M =< X, Y,S,δ,λ> be a finite automaton. Then Theorem 4.4.1 Let M_i =< X_i , Yi , S_i ,δ_i ,λ_i> be a finite automaton,_i = 1,2. Then the path algebra of M₁×M₂ is isomorphic to a subalgebra of which is the tensor product ofTheorem 4.4.2 Let M₁ =< X , Y , S₁ ,δ1 ,λ1> and M₂ =< Y , Z , S₂ ,δ₂ ,λ₂> be finite automata. Then the path algebra F (ΔM M) of M₁ M₂ is isomorphic to a subalgebra ofTheorem 4.4.3 Let M₁ =< X , Y , S₁ ,δ₁ ,λ₁> and M₂ =< Y , Z , S₂ ,δ₂ ,λ₂> be finite automata. Suppose M₁ is weakly_invertible with delayτ1 and M₂ is weakly_invertible with delayτ2. Then there is a subalgebra A of such that A ( rad ( A) )τ₁ +τ₂ +1 is an algebra of dimensionThe last part of this paper is the conclusion. It summarizes the content of this paper and illustrates the further_investigation of this field.