Word-functions of stochastic and pseudo stochastic automata
Paavo Turakainen · Annales Academiae Scientiarum Fennicae Series A I Mathematica · 1975
PAAVO TURAKAINEN L lntroilucti'on' It is well-known that any word-function p" X* -+ 'E of finite rank n canbe written in the form (1) p(P):abuPt(PA(P)+c) YP(X+ rvhere a,,b, c adje constants anrJ ltais a word-function generated by a stochastic automaton.However, in the existing proofs (cf' Ill], [12], [2], [3])the num- ber of states of 1 is much larger than za.The purpose of this paper is to consicler the following problem: what is the minimal value of ft(n) suclt that any word-functionp of runkn can be written in the form (l) for some k(n) -state stochastic automaton 1 ?It is proved that there exists an (n * 2)-state actual doubly stochastic automaton / such that (l) holds for c =--(n | Zl-t _and for some_ pg*i:tiYg "otmtu.tt.a, b.This is donä by modifying the method we used in [Il], [12] rvhere we showed that every pseudo stochastic language is stochastic' It is proved that there exists an (z * 3)-state actual doubly stochastic automaton B such that p(P) -bti.P)@ue) * c) v P (x+ rvhere ö is a positive constant and c : -(n+ 3)-1.Iloreover, B has a fixecl initial state which is also the only final state.In fact this implies that every stochastic language .L is quasidefinite in the sense of Paz [6] and that I/ + {I} is accepted by a stochastic automaton having a fixed initial state which is the same as the only final state.The last mentioned result has been known for pseudo stochastic automata (cf.[10]), but it has been open for stochastic automata.If lp(i.)l ( l, then (2) holds.even for an (za * 2)-state stochastic autom- aton E (c depends on the sign of p(I))' In the general case, the problem concerning the value n * 2 rcmains open.We shory that n and n * I are not possible.