Davis [1] represented the structural synthesis of a stochastic finite-state machine in terms of some relations between finite Markov chains and deterministic finite-state machines. Earlier, Dvoretzky and Wolfowitz [2] proposed a method of stabilizing a discrete input process by using an adder modulo n. Gill [3] restated, in automata-theoretical terms, the problem of transforming a random sequence into a uniform distribution.

In this paper, the authors continue their study (for example, see [4]) of the problem of transforming, by a deterministic finite-state machine, a discrete random process into a discrete uniform distribution, with arbitrarily given accuracy. They introduce a wide class of “superunstable” random sources for which the generated random processes still can be transformed into the uniform distribution &pgr;₀=(1/n,1/n, . . . ,1/n) by an adder modulo n. They prove four main theorems concerning the possibility of stabilization of the output process by a Gill automaton and its rate of stabilization. In particular, they determine new lower bounds on the stabilization rate, which depend on the number of computing steps of the adder when the input process is described by a finite Markov chain.