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.
Read more about this topic: Probabilistic Automaton
Famous quotes containing the word definition:
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)