Realizations by stochastic finite automata

摘要

It is shown that a real-valued function f(x), defined for strings x over a finite alphabet,is of the form (βg(x)+γ) exp(δ|x|) for constants β, γ, δ, and the acceptance probability function g for a probabilistic automation, if and only if f is of finite rank, where the latter external criterion is equivalent to the internal realizability of f by a finite-state sequential system permitted to have arbitrary real initial, transition, and output weights. The development encompasses multiple numerical outputs (finite vectors of functions of strings) and the corresponding generalization of this theorem; as an intermediate step, a set of sufficient conditions is established for equivalence of sequential systems (ss) with multiple outputs, yielding procedures for conversion of ss to numerical-output probabilistic automata (npa). Additional instances are given of application of these ideas in constructing npa equivalent to certain ss.