Automaton, probabilistic

stochastic automaton

A generalization of a finite automaton (cf. Automaton, finite) in which the transition and the output functions are random functions. In other words, a probabilistic automaton may be defined as a system $ (A, S, B, \phi , \psi ) $ where $ A, S, B $ are finite alphabets having the same meaning as for finite automata, while $ \phi , \psi $ are random functions mapping $ S \times A $ into $ S $ and $ B $, respectively, and are represented by systems of probability measures $ \phi _ {s,a} , \psi _ {s,a} $, defined for all $ a $ from $ A $ and $ s $ from $ S $, on $ S $ and $ B $, respectively. These measures are usually given by a stochastic matrix (cf. Automata, methods of specification of). If these probability measures can assume only two values 0 and 1, the concept of a probabilistic automaton is practically identical with that of a deterministic automaton. Autonomous probabilistic automata without output are essentially equivalent to discrete Markov chains. The functioning of a probabilistic automaton is determined similarly to that of a non-deterministic automaton, the initial state being determined by giving a probability measure $ \sigma $ on $ S $. If the probabilistic automaton is in state $ s $ with a certain probability $ p $ and accepts the input letter $ a $, it will, with probability $ p \cdot \omega (s, a, s ^ \prime , b) $ pass into state $ s ^ \prime $, and will output the letter $ b $ of the output alphabet.

As with finite automata, probabilistic automata can be classified into transformers and acceptors, in accordance with their type of behaviour. In the former case the automaton operates by transforming input words into output words and into words in the alphabet of states with certain probabilities. If the words are of the same length, these probabilities form a probability measure, since such behaviour may be regarded as giving a countable system of such measures. In the latter case, a subset $ S ^ { \prime } \subseteq S $ of final states and a number $ \lambda $ from $ [0, 1] $, called the cut point, are given. An event which is representable by the probabilistic acceptor $ \mathfrak A _ \sigma = (A, S, \phi , S ^ { \prime } , \lambda ) $, where $ \phi $ is a random function mapping $ S \times A $ into $ S $ and is defined by a system of probability measures $ \phi _ {s,a} $ defined on $ S $, consists of all words over $ A $ under the effect of which the automaton passes into one of the final states with probability at least $ \lambda $. As distinct from finite automata, probabilistic automata can represent a continuum class of events. Moreover, even a single probabilistic automaton may represent a continuum class of events if $ \lambda $ is varied. If the input alphabet is a one-letter alphabet, each probabilistic automaton merely represents a countable class of events, which also includes irregular events in the general case. At special cut points, the so-called isolated points, the probabilistic automaton represents only regular events. A number $ \lambda $ from the segment $ [0, 1] $ is known as an isolated cut point for this automaton if there exists a positive number $ \delta $ such that for any input word the probability of transforming the probabilistic automaton by this word into its final state differs by at least $ \delta $ from $ \lambda $.

Most of the concepts and problems typical of finite automata may be generalized, in different variants, to probabilistic automata. Many of the concepts and problems preserve the properties of finite automata. For instance, it is possible to introduce the concept of equivalence of states so as to retain the well-known theorem on the possibility of differentiating between states by means of a simple experiment (cf. Automata, experiments with). On the other hand, unlike finite automata, whose minimal form is unambiguously defined (up to an isomorphism), a continuum of equivalent minimal probabilistic automata may exist for a given probabilistic automaton.

There are different ways and means of setting up probabilistic automata. For instance, a probabilistic automaton may be represented by a deterministic automaton with two inputs into one of which is fed a random sequence of input letters. Probabilistic automata are mathematical models of many real mechanisms and are used in studying the behaviour of living organisms.

References

[1]	R.G. Bukharev, "Probabilistic automata" , Kazan' (1970) (In Russian)
[2]	P. Starke, "Abstrakte Automaten" , Deutsch. Verlag Wissenschaft. (1969)