Accession Number : AD0726102
Title : A Decision Problem of Finite State Probabilistic Automata.
Descriptive Note : Interim rept. no. 1, 25 Mar 70-25 Mar 71,
Corporate Author : SYRACUSE UNIV N Y DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
Personal Author(s) : Chen,K. A. ; Hu,Ming K.
Report Date : JUN 1971
Pagination or Media Count : 163
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)
Descriptors : (*LINGUISTICS, AUTOMATA), CONTEXT FREE GRAMMARS, CONTEXT SENSITIVE GRAMMARS, STOCHASTIC PROCESSES, GROUPS(MATHEMATICS), ALGORITHMS, MATRICES(MATHEMATICS), PERMUTATIONS
Subject Categories : Linguistics
Distribution Statement : APPROVED FOR PUBLIC RELEASE