Probabilistic automaton

From Wikipedia, the free encyclopedia
  (Redirected from Probabilistic automata)
Jump to: navigation, search

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.

The concept was introduced by Michael O. Rabin in 1963;[1] 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[edit]

The probabilistic automaton may be defined as an extension of a non-deterministic finite automaton (Q,\Sigma,\delta,q_0,F), together with two probabilities: the probability P of a particular state transition taking place, and with the initial state 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 Q
  • a finite set of input symbols \Sigma
  • a transition function \delta:Q\times\Sigma \to P(Q)
  • a set of states F distinguished as accepting (or final) states F\subset Q.

Here, P(Q) denotes the power set of Q.

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

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

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

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

The matrix \theta_a is then a square matrix, whose entries are zero or one, indicating whether a transition 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 this matrix by a stochastic matrix P, so that the probability of a transition is given by

\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

\sum_{q^\prime}\left[P_a\right]_{qq^\prime}=1

for all input letters a and internal states q. The initial state of a probabilistic automaton is given by a row vector v, whose components add to unity:

\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 abc, would be

v P_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 (Q,\Sigma,P, v, F). A Rabin automaton is one for which the initial distribution v is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one.

Stochastic languages[edit]

The set of languages recognized by probabilistic automata are called stochastic languages. They include the regular languages as a subset.

Let F=Q_\text{accept}\subset Q be the set of "accepting" or "final" states of the automaton. By abuse of notation, Q_\text{accept} can also be understood to be the column vector that is the membership function for Q_\text{accept}; that is, it has a 1 at the places corresponding to elements in 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

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

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

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

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

\vert vP(s)Q_\text{accept} - \eta \vert \ge \delta

for all s\in\Sigma^*

Properties[edit]

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 0<\eta<1.

Every stochastic language is representable by a Rabin automaton.

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

p-adic languages[edit]

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 0,1,2,\ldots,(p-1) such that

L_{\eta}(p)=\{0.n_1n_2n_3 \ldots \vert 0\le n_k<p \text{ and } 
0.n_1n_2n_3\ldots > \eta \}

That is, a p-adic language is merely the set of real numbers, written in base-p, such that they are greater than \eta. It is straightforward to show that all p-adic languages are stochastic. However, a p-adic language is regular if and only if \eta is rational. In particular, this implies that the number of stochastic languages is uncountable.

Generalizations[edit]

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.

References[edit]

  1. ^ M. O Rabin,"Probabilistic Automata", Information and Control 6 (1963) pp. 230–245
  • Arto Salomaa, Theory of Automata (1969) Pergamon Press, Oxford (See chapter 2).