In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the non-deterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix or stochastic matrix. Thus, the probabilistic automaton generalizes the concept of a Markov chain or subshift of finite type. The languages recognized by probabilistic automata are called stochastic languages; these include the regular languages as a subset. The number of stochastic languages is uncountable.
Contents
The concept was introduced by Michael O. Rabin in 1963; a certain special case is sometimes known as the Rabin automaton. In recent years, a variant has been formulated in terms of quantum probabilities, the quantum finite automaton.
Definition
The probabilistic automaton may be defined as an extension of a non-deterministic finite automaton
For the ordinary non-deterministic finite automaton, one has
Here,
By use of currying, the transition function
so that
The matrix
The probabilistic automaton replaces these matrices by a family of stochastic matrices
A state change from some state to any state must occur with probability one, of course, and so one must have
for all input letters
The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string
In particular, the state of a probabilistic automaton is always a stochastic vector, since the product of any two stochastic matrices is a stochastic matrix, and the product of a stochastic vector and a stochastic matrix is again a stochastic vector. This vector is sometimes called the distribution of states, emphasizing that it is a discrete probability distribution.
Formally, the definition of a probabilistic automaton does not require the mechanics of the non-deterministic automaton, which may be dispensed with. Formally, a probabilistic automaton PA is defined as the tuple
Stochastic languages
The set of languages recognized by probabilistic automata are called stochastic languages. They include the regular languages as a subset.
Let
where
A language is called η-stochastic if and only if there exists some PA that recognizes the language, for fixed
A cut-point is said to be an isolated cut-point if and only if there exists a
for all
Properties
Every regular language is stochastic, and more strongly, every regular language is η-stochastic. A weak converse is that every 0-stochastic language is regular; however, the general converse does not hold: there are stochastic languages that are not regular.
Every η-stochastic language is stochastic, for some
Every stochastic language is representable by a Rabin automaton.
If
p-adic languages
The p-adic languages provide an example of a stochastic language that is not regular, and also show that the number of stochastic languages is uncountable. A p-adic language is defined as the set of strings in the letters
That is, a p-adic language is merely the set of real numbers, written in base-p, such that they are greater than
Generalizations
The probabilistic automaton has a geometric interpretation: the state vector can be understood to be a point that lives on the face of the standard simplex, opposite to the orthogonal corner. The transition matrices form a monoid, acting on the point. This may be generalized by having the point be from some general topological space, while the transition matrices are chosen from a collection of operators acting on the topological space, thus forming a semiautomaton. When the cut-point is suitably generalized, one has a topological automaton.
An example of such a generalization is the quantum finite automaton; here, the automaton state is represented by a point in complex projective space, while the transition matrices are a fixed set chosen from the unitary group. The cut-point is understood as a limit on the maximum value of the quantum angle.