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.
[1][2] Thus, the probabilistic automaton also generalizes the concepts of a Markov chain and of a subshift of finite type.
A probabilistic automaton (PA) instead has a weighted set (or vector) of next states, where the weights must sum to 1 and therefore can be interpreted as probabilities (making it a stochastic vector).
The notions states and acceptance must also be modified to reflect the introduction of these weights.
A PA is in some sense a half-way step from deterministic to non-deterministic, as it allows a set of next states but with restrictions on their weights.
However, this is somewhat misleading, as the PA utilizes the notion of the real numbers to define the weights, which is absent in the definition of both DFAs and NFAs.
replaced by a stochastic vector giving the probability of the automaton being in a given initial state.
of a non-deterministic finite automaton can be written as a membership function so that
is then a square matrix, whose entries are zero or one, indicating whether a transition
Such a transition matrix is always defined for a non-deterministic finite automaton.
The initial state of a probabilistic automaton is given by a row vector
, whose components are the probabilities of the individual initial states
, that add to 1: The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string
Formally, a probabilistic automaton PA is defined as the tuple
be the set of "accepting" or "final" states of the automaton.
can also be understood to be the column vector that is the membership function for
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
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 representable by a Rabin automaton.
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 in [0, 1], written in base-p, such that they are greater than
It is straightforward to show that all p-adic languages are stochastic.
[3] In particular, this implies that the number of stochastic languages is uncountable.
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.