# 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;[1] 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 ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$, together with two probabilities: the probability ${\displaystyle P}$ of a particular state transition taking place, and with the initial state ${\displaystyle q_{0}}$ 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

• a finite set of states ${\displaystyle Q}$
• a finite set of input symbols ${\displaystyle \Sigma }$
• a transition function ${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$
• a set of states ${\displaystyle F}$ distinguished as accepting (or final) states ${\displaystyle F\subseteq Q}$.

Here, ${\displaystyle \wp (Q)}$ denotes the power set of ${\displaystyle Q}$.

By use of currying, the transition function ${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$ of a non-deterministic finite automaton can be written as a membership function

${\displaystyle \delta :Q\times \Sigma \times Q\to \{0,1\}}$

so that ${\displaystyle \delta (q,a,q^{\prime })=1}$ if ${\displaystyle q^{\prime }\in \delta (q,a)}$ and ${\displaystyle \delta (q,a,q^{\prime })=0}$ if ${\displaystyle q^{\prime }\notin \delta (q,a)}$. The curried transition function can be understood to be a matrix with matrix entries

${\displaystyle \left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })}$

The matrix ${\displaystyle \theta _{a}}$ is then a square matrix, whose entries are zero or one, indicating whether a transition ${\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$ 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 ${\displaystyle P_{a}}$, for each symbol a in the alphabet ${\displaystyle \Sigma }$ so that the probability of a transition is given by

${\displaystyle \left[P_{a}\right]_{qq^{\prime }}}$

A state change from some state to any state must occur with probability one, of course, and so one must have

${\displaystyle \sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1}$

for all input letters ${\displaystyle a}$ and internal states ${\displaystyle q}$. The initial state of a probabilistic automaton is given by a row vector ${\displaystyle v}$, whose components are the probabilities of the individual initial states ${\displaystyle q}$, that add to 1:

${\displaystyle \sum _{q}\left[v\right]_{q}=1}$

The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string ${\displaystyle abc}$, would be

${\displaystyle vP_{a}P_{b}P_{c}}$

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 ${\displaystyle (Q,\Sigma ,P,v,F)}$. A Rabin automaton is one for which the initial distribution ${\displaystyle v}$ 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 ${\displaystyle F=Q_{\text{accept}}\subseteq Q}$ be the set of "accepting" or "final" states of the automaton. By abuse of notation, ${\displaystyle Q_{\text{accept}}}$ can also be understood to be the column vector that is the membership function for ${\displaystyle Q_{\text{accept}}}$; that is, it has a 1 at the places corresponding to elements in ${\displaystyle Q_{\text{accept}}}$, 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

${\displaystyle L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}}$

where ${\displaystyle \Sigma ^{*}}$ is the set of all strings in the alphabet ${\displaystyle \Sigma }$ (so that * is the Kleene star). The language depends on the value of the cut-point ${\displaystyle \eta }$, normally taken to be in the range ${\displaystyle 0\leq \eta <1}$.

A language is called η-stochastic if and only if there exists some PA that recognizes the language, for fixed ${\displaystyle \eta }$. A language is called stochastic if and only if there is some ${\displaystyle 0\leq \eta <1}$ for which ${\displaystyle L_{\eta }}$ is η-stochastic.

A cut-point is said to be an isolated cut-point if and only if there exists a ${\displaystyle \delta >0}$ such that

${\displaystyle \vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta }$

for all ${\displaystyle s\in \Sigma ^{*}}$

## 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 ${\displaystyle 0<\eta <1}$.

Every stochastic language is representable by a Rabin automaton.

If ${\displaystyle \eta }$ is an isolated cut-point, then ${\displaystyle L_{\eta }}$ is a regular language.

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

${\displaystyle L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}\eta \}}$

in the letters ${\displaystyle 0,1,2,\ldots ,(p-1)}$.

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 ${\displaystyle \eta }$. 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 ${\displaystyle \eta }$ 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.

## Notes

1. ^ Michael O. Rabin (1963). "Probabilistic Automata". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0.