Automata in Random Environments 1

Abstract

In Gould and Wegman (1977), a model of a system located within an environment was introduced in which the transition function of the system is not only related to the present state and input, but also to the present configuration of the environment.

In this paper we shall consider the case of automata operating within random environments. In contrast to the previous case, where we suppose we can control the environment, we shall assume that the realization of the environment is governed by some probabilistic structure. Hence, the sequence of environment configurations is a stochastic process.

In considering automata in random environments (ARE) there is a dual nature to the randomness, the environment sequence is random and for each value the environment sequence assumes, the probabilistic state transitions are defined. In the ARE case the relative frequency of acceptance of a tape under a fixed random environment sequence estimates the expected acceptance probability. Accordingly, the notion of expected acceptance sets is defined. Finally, a mean equivalent canonical representation for automata in random environments which eliminates the randomness due to the probabilistic state transitions is formulated. That is, for any ARE with finite environment set, deterministic assignment of the initial state, and deterministic transitions which has a state distribution equivalent in the mean.

This formulation of automata in random environments is useful when only certain probabilistic assumptions about the occurrence of any environment configuration can be made or when the environment configuration can only be measured by statistical techniques.