Probabilistic automaton

In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the nondeterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix. Thus, the probabilistic automaton also generalizes the concepts of a Markov chain and of a 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.
The concept was introduced by Michael O. Rabin in 1963; a certain special case is sometimes known as the Rabin automaton (not to be confused with the subclass of ω-automata also referred to as Rabin automata). 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 nondeterministic finite automaton formula_1, together with two probabilities: the probability formula_2 of a particular state transition taking place, and with the initial state formula_3 replaced by a stochastic vector giving the probability of the automaton being in a given initial state.
For the ordinary non-deterministic finite automaton, one has
Here, formula_9 denotes the power set of formula_4.
By use of currying, the transition function formula_6 of a non-deterministic finite automaton can be written as a membership function
so that formula_13 if formula_14 and formula_15 if formula_16. The curried transition function can be understood to be a matrix with matrix entries
The matrix formula_18 is then a square matrix, whose entries are zero or one, indicating whether a transition formula_19 is allowed by the NFA. Such a transition matrix is always defined for a non-deterministic finite automaton.
The probabilistic automaton replaces these matrices by a family of right stochastic matrices formula_20, for each symbol a in the alphabet formula_5 so that the probability of a transition is given by
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 formula_24 and internal states formula_25. The initial state of a probabilistic automaton is given by a row vector formula_26, whose components are the probabilities of the individual initial states formula_25, that add to 1:
The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string formula_29, would be
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 formula_31. A Rabin automaton is one for which the initial distribution formula_26 is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one.
Stochastic languages.
The set of languages recognized by probabilistic automata are called stochastic languages. They include the regular languages as a subset.
Let formula_33 be the set of "accepting" or "final" states of the automaton. By abuse of notation, formula_34 can also be understood to be the column vector that is the membership function for formula_34; that is, it has a 1 at the places corresponding to elements in formula_34, and a zero otherwise. This vector may be contracted with the internal state probability, to form a scalar. The language recognized by a specific automaton is then defined as
where formula_38 is the set of all strings in the alphabet formula_5 (so that * is the Kleene star). The language depends on the value of the cut-point formula_40, normally taken to be in the range formula_41.
A language is called "η"-stochastic if and only if there exists some PA that recognizes the language, for fixed formula_40. A language is called stochastic if and only if there is some formula_41 for which formula_44 is "η"-stochastic.
A cut-point is said to be an isolated cut-point if and only if there exists a formula_45 such that
for all formula_47
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 formula_48.
Every stochastic language is representable by a Rabin automaton.
If formula_40 is an isolated cut-point, then formula_44 is a regular language.
"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 formula_52.
That is, a "p"-adic language is merely the set of real numbers in [0, 1], written in base-"p", such that they are greater than formula_40. It is straightforward to show that all "p"-adic languages are stochastic. In particular, this implies that the number of stochastic languages is uncountable. A "p"-adic language is regular if and only if formula_40 is rational.
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.