Probabilistic Automaton - Definition

Definition

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

Here, denotes the power set of .

By use of currying, the transition function of a non-deterministic finite automaton can be written as a membership function

so that if and if . The curried transition function can be understood to be a matrix with matrix entries

The matrix is then a square matrix, whose entries are zero or one, indicating whether a transition 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, 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 and internal states . The initial state of a probabilistic automaton is given by a row vector, whose components add to unity:

The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string, 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 . A Rabin automaton is one for which the initial distribution is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one.