| Automata theory is a mathematical theory which studies the functions, the structures of the discrete system and the relationships between them, and also it is an abstract of many specific discrete digital systems. Automata theory is a subject based on the Switching network theory and Turning machine theory of the mathematical logic. Probabilistic finite automata is a branch of automata theory, it is different from non-probabilistic finite automata in that the actions of probabilistic finite automata are random. The major investigation of probabilistic finite automata is similar to that of general automatic theory. They both include the probabilistic Turing machine, the probabilistic sequential machine and the probabilistic recognizer etc. The results obtained have extended the previous results of the automata and also have proposed a lot of new questions, thus the results obtained have enriched the contents of the automata theory.In this paper, algebraic structure of the probabilistic finite automata and the relationships between quotient probabilistic finite automata and probabilistic finite automata homomorphism have been discussed from the view of the algebra; the Homomorphism decomposition theorem is proved; a decomposition of a class of probabilistic finite automata is obtained, and the mutual relations between several products in depth is further discussed.This paper is composed of five chapters.In chapter 1, the definitions of probabilistic finite automata and finite automata are introduced, and the idea of this paper is set forth. In addition, the basic concepts and the marks of this paper are also introduced.In chapter 2 ,the relationship between the quotient probabilistic finite automata and probabilistic finite automata homomorphism is discussed. The main results are as follows:Proposition 2.1.4 Let M =< X , Q , Y ,P> be a uniform probabilistic finite automaton, then M is irreducible if and only if Q≤2.Theorem 2.2.1 Let M =< X , Q , Y ,P> be a probabilistic finite automaton,Ï€ 1 ,Ï€ 2 are effective partition of M such thatÏ€ 1≤π2, then Theorem 2.2.6 Let M =< X , Q , Y ,P> be a probabilistic finite automaton.then there is a one-to-one onto correspondence between the quotient probabilistic finite automata of M and the probabilistic finite automata homomorphism inage of M .Theorem 2.2.7 (homomorphism decomposition theorem of probabilistic finite automata) Let M1 =< X , Q1 , Y ,P1> , M2 =< X , Q2 , Y ,P2> and M3 =< X , Q3 , Y ,P3> be probabilistic finite automata, M2≤M1, M 3≤M1, ? : M1â†'M2 andψ: M2â†'3 be two homomorphisms, then there is a homomorphismθ: M2â†'M3 such thatψ=θ? if and only if the effective partitionÏ€ 1 induct by ? of M1 and the effective partitionÏ€ induct byψof M1 satisfyÏ€ 1≤π.Theorem 2.2.8 Let M1 =< X , Q1 , Y ,P1> and M2 =< X , Q2 , Y ,P2> be probabilistic finite automata, M2≤M1,? be a homomorphism with ? :M1â†'M2. IfÏ€ 2 = { H ii = 1,2, L , n} is an effective partition of M2, then }1Ï€ 1 = { K i K i = ? ?( H i ),Hi∈π2is an effective partition of M1with respect to 2 1In chapter 3, three kinds of products of probabilistic finite automata are given, and they are used to decompose special probabilistic finite automata. The main results are as follows: Theorem 3.1.2 Let M1 =< X , Q1 , Y1 ,P1> , M2 =< X , Q2 , Y2 ,P2> , N1 =< Z1 , R1 , U 1 ,P1′> and N 2 =< Z 2 , R2 , U 2 ,P2′> be probabilistic finite automata, if M2≤wM1, N 2≤wN1,thenâ…°) M2×N 2≤wM1×N1;â…±) if M =< X , Q , Y ,P>, then M×N 2≤wM×N1.Theorem 3.3.1 Let M =< X , Q , Y ,P> be a uniform probabilistic finite automaton, then M can be decomposed into a series product of a uniform probabilistic finite automata with one state and a Markov chain.Theorem 3.3.4 Let M =< X , Q , Y ,P> be a uniform probabilistic finite automaton, then M can be decomposed into a series product of a random source code, a Bernoulli Process and some defend finite automata.Theorem 3.3.5 Let M1 =< X 1 , Q1 , Y1 ,P1> and M2 =< X 2 , Q2 , Y2 ,P2> be probabilistic finite automata, and { }Ï€ 1 = H ii = 1,2, L ,n, { }Ï€ 2 = K jj = 1,2, L ,m be effective partition of M1 and M2 respectively, then { }Ï€ 1×π 2 = ( H i , K j ) H i∈π 1 ,Kj∈π2 is an effective partition In chapter 4, several products of probabilistic finite automata were given, and focus on the homomorphism relationship between them. The main results are as follows: Theorem 4.2.1 Let M1 =< X 1 , Q1 , Y1 ,P1> , M2 =< X 2 , Q2 , Y2 ,P2> and M 3 =< X 3 , Q3 , Y3 ,P3> be probabilistic finite automata, thenTheorem 4.2.2 Let M1 =< X 1 , Q1 , Y1 ,P1> and M2 =< X2 , Q2 , Y2 ,P2> be probabilistic finite automata, such that P2 ( q2 , x2 , q2′, y2 ) = P2 ( q2 , x2′, q2′, y2) for all q2 ,q2′∈Q2, x2 ,x2′∈X2 and y 2∈Y2,then M1ωM2≤wM1 o M2.Theorem 4.2.4 Let M =< X , Q , Y ,P> , M1 =< X1 , Q1 , Y1 ,P1> and M2 =< X2 , Q2 , Y2 ,P2> be probabilistic finite automata and M1≤wM2, then M o M1≤wM o M2.Chapter 5 is the conclusion part. It summarizes the main results of this paper. The meaning of this paper and the further investigation of this field are illustrated. |
PDF Full Text Request