A decision problem of finite state probabilistic automata

Abstract : It is shown that nonregular languages can be accepted by finite state probabilistic automata. For many years it was not known whether a finite state probabilistic automaton existed which would accept a context sensitive language that is not context free. Such a finite state probabilistic automaton is constructed and the above question is clarified. It is known that the problem of determining for an arbitrary finite state probabilistic automaton whether the set of words accepted by the automaton is regular, is recursively unsolvable. However, a related problem, namely to determine for an arbitrary finite state probabilistic automaton whether the total number of distinct state transition matrices of the automaton is finite, is solvable. An algorithm for solving this problem is presented in this report. The equivalent problem in mathematics is to decide when a stochastic semigroup with a finite number of generators is finite. In the process of presenting the algorithm, the concept of generalized permutation matrices is introduced. The set of generalized permutation matrices for a given matrix forms a semigroup, but not a group. The concept of generalized permutation matrices gives insight into the reason why a finite state probabilistic automaton has a finite number of distinct state transition matrices. (Author)